Background

You in Bit Town are going to Hex Town to meet your npy.

Problem Description

There are $n$ towns in your country (numbered from $1$ to $n$) and $m$ bidirectional roads. Bit Town is at node $a$, and Hex Town is at node $b$. Each road has a length. Since you know the map very well, you have found the shortest path between the two towns, and you decide to call this path the lucky path.

One day, the government decides to do construction on the roads. To keep traffic running, they decide to close only one road at a time (a closed road cannot be used).

For every road on this lucky path, you want to know the shortest distance from Bit Town to Hex Town when that road is closed.

Input Format

The first line contains 4 integers: $n,m,a,b$, representing the number of towns, the number of roads, the index of Bit Town, and the index of Hex Town.

The next $m$ lines describe the roads. The $i$-th line contains three integers $u_i,v_i,w_i$: towns $u_i$ and $v_i$ are connected by a road of length $w_i$.

The last line contains a number $k$ and $k$ numbers: $(v_1(=a),v_2,\dots,v_{k}(=b))$, describing the lucky path. $v_i(1\le i\le k)$ is the index of the $i$-th node on the lucky path.

Output Format

Output $k-1$ lines in total.

For each $t=1\dots k-1$, output one integer on one line: when the road $(v_t,v_{t+1})$ is under construction (closed), the length of the shortest path between Bit Town and Hex Town. If the path does not exist, output -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

Hint

Constraints

Subtask#0 is the sample.

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

For $i\neq j$, it holds that $u_i\neq u_j$ or $v_i\neq v_j$.

Sample Explanation

After closing road $(1,2)$, Bit Town at node $1$ cannot reach Hex Town at node $5$.

After closing road $(2,3)$, the shortest path from Bit Town at node $1$ to Hex Town at node $5$ is $1\rightarrow 2\rightarrow5$, with length $1+100=101$.

After closing road $(3,5)$, the shortest path from Bit Town at node $1$ to Hex Town at node $5$ is $1\rightarrow 2\rightarrow3\rightarrow4\rightarrow5$, with length $1+3+3+3=10$。

Translated by ChatGPT 5