题目背景

Bit 镇的你要去 Hex 镇找你的 npy。

题目描述

你所在的国家有 $n$ 个镇（镇从 $1$ 到 $n$ 编号），$m$ 条双向道路，Bit 镇在 $a$ 点，Hex 镇在 $b$ 点。每条道路有一个长度。你很了解周围的地图，所以找到了两个镇之间的最短路径，而且，决定将这条路径称为幸运路径。

有一天，政府决定在公路上施工，为了维持交通，决定每次只关闭一条道路（关闭后道路不可通行）。

对于这条幸运路径上的每一条道路，你想知道当这条道路正在关闭时从 Bit 镇到 Hex 镇的最短距离。

输入格式

输入的第一行由 4 个整数组成：$n,m,a,b$，分别表示城镇数量，道路数量，Bit 镇编号，Hex 镇编号。

接下来的 $m$ 行，第 $i$ 行包含三个整数 $u_i,v_i,w_i$ ：城镇 $u_i$ 和城镇 $v_i$ 由长度为 $w_i$ 的道路连接。

输入的最后一行由数字 $k$ 和 $k$ 个数字组成：$(v_1(=a),v_2,\dots,v_{k}(=b))$ ，表示幸运路径。 $v_i(1\le i\le k)$ 表示幸运路径上的第 $i$ 个点的编号。

输出格式

输出共 $k-1$ 行。

对于每个 $t=1\dots k-1$，输出一行一个整数：道路 $(v_t,v_{t+1})$ 施工时，Bit 镇和 Hex 镇之间的最短路径的长度。如果路径不存在，则输出 -1。

5 6 1 5 
1 2 1 
2 3 3 
2 5 100 
3 4 3 
3 5 5 
4 5 3 
4 1 2 3 5

-1 
101 
10

提示

数据范围：

Subtask#0 为样例。

$1\le n\le 2000$，$1\le m\le10^5$，$1\le u_i,v_i\le n$，$1\le w_i\le10^5$。

对于 $i\neq j$，满足 $u_i\neq u_j$ 或 $v_i\neq v_j$。

样例解释：

封闭道路 $(1,2)$ 后从点 $1$ 的 Bit 镇无法到达点 $5$ 的 Hex 镇。

封闭道路 $(2,3)$ 后从点 $1$ 的 Bit 镇到点 $5$ 的 Hex 镇的最短路为 $1\rightarrow 2\rightarrow5$，长度 $1+100=101$。

封闭道路 $(3,5)$ 后从点 $1$ 的 Bit 镇到点 $5$ 的 Hex 镇的最短路为 $1\rightarrow 2\rightarrow3\rightarrow4\rightarrow5$，长度 $1+3+3+3=10$。