0 Judge
Code: 0
Since the economic fluctuation is becoming more and more severe, the traffic management bureau finally decides to adjust the fee tolled by the tolling stations in the road system daily.
The road system is modeled as an undirected graph of $N$ vertices and $M$ edges, where vertices represent towns and edges represent bi-directional roads connecting two towns. A driver is charged whenever passing through a road in either direction. Besides, a charge will also be made whenever a driver passes through a town with tolling station. The fee charged when passing through a road is fixed, while the charge made by passing through a tolling station varies from day to day. However, every tolling station charges the same fee on the same day.
It is your task to evaluate the minimum toll charged on each day when travelling from town $1$ to town $N$.
The first line of the input contains an integer $T$, the number of test cases. Each test case is formatted as follows.
$N\;M\;T\;Q$
$u_{1}\;v_{1}\;c_{1}$
$u_{2}\;v_{2}\;c_{2}$
$\vdots$
$u_{E}\;v_{E}\;c_{E}$
$t_{1}\;t_{2}\;\cdots\;t_{T}$
$q_{1}\;q_{2}\;\cdots\;q_{Q}$
The first line of each test case consists of 4 integers $N$ ($3 \leq N \leq 1000$), $M$ ($1 \leq M \leq 2000$), $T$ ($1 \leq T \leq 100$) and $Q$ ($1 \leq Q \leq 10^{5}$) representing the number of towns, the number of roads, the number of towns with tolling station and the number of days considered, respectively.
Each of the following $M$ lines contains three integers $u_i$, $v_i$ ($1 \leq u_i, v_i \leq N$), and $c_i$ ($1 \leq c_i \leq 10^{9}$), representing a bi-directional road connecting town $u_i$ and $v_i$, and fee $c_i$ is charged whenever passing through this road.
After that follows a line containing $T$ space-separated integers $t_i$ ($1 \leq t_i \leq N$), representing the towns with tolling stations. Finally, a line of $Q$ space-separated integers $q_i$ ($0 \leq q_i \leq 10^{9}$) follows, representing the tolling fee made whenever passing through a tolling station on the $i^{th}$ day.
You may assume that each of the towns is reachable from any other towns in the road system. Besides, neither town $1$ nor town $N$ will be the tolling station.
For each test case, output $Q$ space-separated integers $ans_1$, $ans_2$, $\cdots$, $ans_Q$, where the $i^{th}$ integer is the minimum toll charged on the $i^{th}$ day when travelling from town $1$ to town $N$, in a line.
4
7 10 3 8
1 2 7
1 3 1
1 4 9
2 6 8
3 5 1
4 5 1
4 6 1
5 6 4
5 7 5
6 7 1
3 4 5
0 1 2 3 4 5 6 7
5 5 3 2
1 2 1
1 5 14
2 3 2
3 4 2
4 5 1
2 3 4
2 3
4 5 2 2
1 2 2
1 3 2
2 3 5
2 4 4
3 4 3
2 3
0 1000000000
6 7 2 2
1 2 2
1 3 500000004
2 4 500000005
2 5 5
3 5 500000005
4 6 500000005
5 6 3
2 5
0 1000000000
5 8 11 13 15 16 16 16
12 14
5 1000000005
10 2000000010
no