UOJ Logo Universal Online Judge

UOJ

附件下载 统计

“人在 UOI,刚下飞机”——hehe 蚤刚到下山市,便迫不及待地想和从各地赶来参加 UOI 的网友们面基。

下山市可以简化为一张 $n$ 个点 $m$ 条边的无向图,点用 $1$ 到 $n$ 标号,而第 $i$ 条边连接点 $u_i$ 和 $v_i$,长度为 $w_i$。

hehe 蚤初始在 $1$ 号点,他想要依次和 $k$ 个网友面基,第 $i$ 个网友初始在点 $p_i$。

hehe 蚤和网友们都是匀速走路的。hehe 蚤一秒可以走过 $1$ 单位长度,而他的网友们同样一秒可以走过 $1$ 单位长度。

当 hehe 蚤和一个或多个网友处于同一位置时,他们可以立刻面基,且面基不需要耗时。

hehe 蚤想知道,如果他和网友按照一个商量好的策略行动,那么他和所有网友顺次面基最少需要花费多少秒。

若这个时间为 $T$,你只需输出 $2T$(容易证明这一定是一个整数)。

请注意,时间和边都是连续的,这意味着所有角色可以在边的中间面基、在边上折返和在点上或边中间停留,面基和折返等行动也可以发生在非整数秒。 例如有一条长度为 $1$ 的边,hehe 蚤和 $1$ 号网友分别在两端,他们可以在 $0.5$ 秒后在边正中央面基,随后 hehe 蚤可以花 $0.5$ 秒返回起点。

输入格式

第一行为两个整数 $n, m$,依次为图的点数、边数。

接下来每行有三个整数 $u_i, v_i, w_i$,表示有一条连接 $u_i$ 和 $v_i$ 且长度为 $w_i$ 的边。

接下来为一个整数 $k$。

接下来的一行, $k$ 个整数。其中第 $i$ 个表示第 $i$ 个网友初始所在位置。

输出格式

一个整数 $2T$。

样例一

input

4 6
1 4 4
2 3 4
3 4 1
3 1 2
1 2 1
2 4 4
2
2 3

output

3

explanation

hehe 蚤首先在原地停留 $1$ 秒,$1$ 号网友经过边 $(2,1,1)$ 来到 $1$ 号点和 hehe 蚤面基。

随后 hehe 蚤花 $0.5$ 秒走到边 $(3,1,2)$ 靠近 $1$ 的四分点处,若 $2$ 号网友从一开始就向这个点走,此时他们恰好相遇,完成面基。

可以证明不存在少于 $1.5$ 秒的方案。

样例二、三、四

见下发文件,这三个样例分别满足子任务 $1,2,3$ 的限制。

数据范围

子任务编号 $n \leq$ $m \leq$ $k \leq$ 特殊性质 分值
$1$ $200$ $2000$ $6$ 边权全为 $1$ $30$
$2$ $200$ $n - 1$ $6$ $i$ 和 $i + 1$ 之间有边 $20$
$3$ $200$ $2000$ $6$ $15$
$4$ $10^5$ $2 \times 10^5$ $6$ $20$
$5$ $10^5$ $2 \times 10^5$ $20$ $15$

对于所有数据,保证 $2 \leq n \leq 10^5, n - 1 \leq m \leq 2 \times 10^5, 1 \leq k \leq 20, 1 \leq u, v, p_i \leq n, 1 \leq w \leq 10^6$;保证图连通且无自环、重边。

时间限制:$3\texttt{s}$

空间限制:$512\texttt{MB}$