“人在 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$ 的限制。

数据范围

对于所有数据，保证 $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}$