E. Electric Vehicle Revisited
time limit per test
4 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

This story is a work of fiction. Any similarity to real persons or events is coincidental.

After competing in the regional contest of the Fruit Kingdom, the team vegetable_advantages officially concluded their ICPC journey. However, this was also a new beginning because they wanted to give back to society: whenever they saw a problem, they would try to make it harder. While waiting for their flight back from the Fruit Kingdom to the Vegetable Kingdom, they happened to see this problem (which originated from 2025 National High School Programming Contest Problem C):

"A-Ming bought an electric vehicle with a battery capacity of $$$B$$$. A-Ming knows the initial battery level $$$b$$$, and he wants to plan a route from the starting point $$$s$$$ to the destination $$$t$$$ such that the total charging cost is as low as possible.

The electric vehicle consumes battery power on certain road segments (such as flat roads or uphill roads) and charges the battery on other road segments (such as downhill roads). These charging road segments are completely free of charge. We represent the map using a directed graph, where the weight of an edge indicates the increase or decrease in battery level when driving across this edge. If driving through this edge charges the battery, the weight is a positive integer; conversely, if it consumes power, the weight is a negative integer. We assume that the graph has no positive cycles.

While driving, the electric vehicle's battery level must always remain greater than or equal to $$$0$$$, and no matter how much it charges, the battery level can at most reach $$$B$$$. More specifically, let $$$p$$$ be the current battery level of the electric vehicle, and consider an edge with weight $$$w$$$: if $$$w$$$ is non-negative, the electric vehicle can definitely drive through this edge (even if the battery level $$$p=0$$$), and the remaining battery level will be $$$\min(B, p+w)$$$; if $$$w$$$ is negative and $$$p+w \ge 0$$$, the electric vehicle can drive through this edge, and the remaining battery level after passing through will be $$$p+w$$$; however, if $$$p+w \lt 0$$$, the electric vehicle cannot drive through this edge.

Some vertices on the map are charging stations. A-Ming can pass through multiple charging stations. Because charging takes time to find a charging pile, A-Ming decided to use at most one charging station to charge during the entire trip. Charging one unit of battery at a charging station costs one dollar. A-Ming's goal is to reach the destination while spending the least amount of money."

Cabbage, a member of vegetable_advantages, felt that A-Ming was far too lazy for being willing to use only one charging station! Besides, isn't A-Ming curious about the answers from the fixed starting point $$$s$$$ to every possible destination $$$t=1,2,\dots,n$$$? Therefore, on the plane, they solved the version where one can charge at any number of charging stations and must output the answers for $$$t=1,2,\dots,n$$$, and decided to use it to test you.

Input

The first line contains three integers $$$n,m,s$$$, representing the number of vertices in the map, the number of edges, and the vertex index of the starting point, respectively.

The second line contains two integers $$$B,b$$$, representing the battery capacity and the initial battery level, respectively.

The following $$$m$$$ lines each contain three integers $$$u_i,v_i,w_i$$$, representing that the $$$i$$$-th edge goes from vertex $$$u_i$$$ to vertex $$$v_i$$$ with weight $$$w_i$$$.

The first integer of the last line is $$$g$$$, representing the number of charging stations. This is followed by $$$g$$$ integers $$$p_1,p_2,\dots,p_g$$$, representing the vertex indices where the charging stations are located.

  • $$$1 \le n\le 2\,000$$$
  • $$$1 \le m\le 10^4$$$
  • $$$1 \le s\le n$$$
  • $$$1 \le B\le 10^9$$$
  • $$$0 \le b\le B$$$
  • $$$1 \le u_i, v_i\le n$$$, and $$$u_i \neq v_i$$$
  • $$$-10^9 \le w_i\le 10^9$$$
  • $$$0 \le g\le n$$$
  • $$$1 \le p_1 \lt p_2 \lt \dots \lt p_g \le n$$$
  • It is guaranteed that there is no positive cycle in the graph.
Output

Output $$$n$$$ integers, where the $$$i$$$-th integer represents the minimum amount of money A-Ming must spend to reach the destination when he can use any number of charging stations and $$$t = i$$$. If it is impossible to reach $$$t$$$, output $$$-1$$$.

Examples
Input
7 7 1
100 20
1 2 -10
2 3 -5
3 4 -20
3 5 -30
4 6 -40
5 6 -10
6 7 20
1 3
Output
0
0
0
15
25
35
35
Input
5 4 1
1 0
1 2 -1
2 3 -1
3 4 -1
4 5 -1
5 1 2 3 4 5
Output
0
1
2
3
4
Input
4 3 2
1 0
2 1 0
1 3 -1
4 1 1
0
Output
0
0
-1
-1
Note

In Sample 1, A-Ming is initially at vertex $$$s=1$$$ with an initial battery level of $$$b=20$$$.

For each $$$t \in \{1, 2, 3\}$$$, there is only one path from $$$s$$$ to $$$t$$$, and the initial battery level is sufficient for A-Ming to complete the journey without charging.

For each $$$t \in \{4, 5\}$$$, there is also only one path from $$$s$$$ to $$$t$$$, but the initial battery level is insufficient. Thus, A-Ming has to charge his battery at vertex 3, which costs 15 dollars for $$$t=4$$$ and 25 dollars for $$$t=5$$$.

For $$$t=6$$$, A-Ming takes the path $$$1 \to 2 \to 3 \to 5 \to 6$$$. He charges at vertex 3 up to a battery level of 40 so that he can traverse the edges $$$(3,5)$$$ and $$$(5,6)$$$. This costs 35 dollars.

For $$$t=7$$$, A-Ming takes the path $$$1 \to 2 \to 3 \to 5 \to 6 \to 7$$$ and spends 35 dollars at vertex 3.