Nikola lives in Bittown and he is in love with his girlfriend Anita from a town called Hextown. Nikola knows the country map very well, and he found the shortest path between these two towns. He calls this path lucky path. The map of the country can be described as a collection of towns connected with bidirectional roads.

One day the president of this country decided that there are going to be some works on the roads. In order to uphold the traffic in the country, only one road is going to be closed per day.

For each road on the lucky path, Nikola wants to know the length of the shortest path between Anita and him if that road is closed.

Input

The first line of input contains four integers: n - the number of cities, m - the number of roads between these towns, a - index of town Bittown where Nikola lives, b - the index of town Hextown where Anita lives. Towns are indexed with numbers 1, 2 ... n. Next m lines specify roads: each line contains three integers: u, v and w - there exist road between towns u and v with length w.

Last line of the input contains number k followed by k numbers a = v₁, v₂ ... v_k = b - the lucky path that Nikola uses. 

Output

For every integer t = 1 ... k - 1, in separate line, print the length of the shortest path between cities a and b, if the road (v_t, v_{t + 1}) is closed. If there is no such path, output “-1” without quotes. 

Example

Input:
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

Output:
-1
101
10

Constraints

• -1 ≤ n ≤ 2000, 1 ≤ m ≤ 100,000
• 1 ≤ a, b ≤ n
• 1 ≤ w ≤ 100,000
• There is at most one road between each pair of cities.
• You may assume that the given path is one of the shortest paths that connects given two cities a and b.