G. Grisi Maps
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

The marathonists want to walk to the IC at Unicamp, starting from some other place in Campinas. Instead of using GPS, they rely on Grisi, who claims to know how to get anywhere. Grisi always follows the same strategy to reach any destination: from the main entrance of Unicamp, he knows the best way to reach any location in the neighborhood (and vice versa—he knows the best way to get from any location in the neighborhood to the main entrance). So, he always first goes to the main entrance and then to the destination (using the optimal path for both segments).

Given the graph (undirected and connected) representing the neighborhood, the vertex corresponding to the main entrance of Unicamp, the vertex corresponding to the IC, and multiple queries of the form $$$x$$$, representing that the marathonists want to go from vertex $$$x$$$ to the IC, determine for each query how much extra time they will take to reach the IC from $$$x$$$ by following Grisi's strategy instead of using GPS (which would provide the shortest possible path).

Input

The first line of the input consists of five integers $$$n$$$, $$$m$$$, $$$q$$$$$$(2\le n, m \le 2\cdot 10^5, 1 \le q \le 2\cdot 10^5)$$$, $$$X_1$$$, $$$X_2$$$$$$(1 \le X_1, X_2 \le n)$$$, representing the number of vertices, edges, queries, the vertex of Unicamp's main entrance, and the IC at Unicamp, respectively.

The next m lines each consist of three integers $$$u$$$, $$$v$$$, $$$w$$$$$$(1 \le u, v \le n, 1 \le w \le 1\cdot 10^9)$$$, representing an edge connecting vertices $$$u$$$ and $$$v$$$ with a cost of $$$w$$$ time units.

Each of the last $$$q$$$ lines consists of a single integer $$$x$$$, representing the vertex from which the marathonists will depart.

Output

The output consists of $$$q$$$ lines, where the $$$i$$$-th line indicates the extra time, compared to the GPS route, that the marathonists took to travel from vertex $$$x$$$ to the IC at Unicamp following Grisi's method. If the marathonists are already at the IC, the output should be 0.

Example
Input
4 4 2 1 4
1 2 1
1 3 1
2 4 1
3 4 1
2
3
Output
2
2