Shortest Time to School

In city C, there is an undirected graph with $n$ nodes and $m$ edges. The nodes are numbered $1, 2, \ldots, n$, and for each edge $i$ ($1 \leq i \leq m$), it connects node $u_i$ and node $v_i$ with a length of $l_i$ meters. The school is located at node $s$. There are $q$ students. For the $i$-th student, his/her home is at node $h_i$, and he/she walks at a speed of 1 meter per second. Your task is to compute the minimum number of seconds required for each student to reach the school, assuming they take the shortest possible path.

inputFormat

The first line contains three integers $n$, $m$, and $s$ ($1 \leq s \leq n$).

Each of the next $m$ lines contains three integers $u_i$, $v_i$, and $l_i$, describing an undirected edge between nodes $u_i$ and $v_i$ with length $l_i$ meters ($1 \leq u_i, v_i \leq n$, $l_i > 0$).

The next line contains an integer $q$, the number of queries (i.e., the number of students).

Each of the next $q$ lines contains one integer $h_i$, representing the home node of the $i$-th student.

outputFormat

Output $q$ lines. The $i$-th line should contain one integer: the minimum number of seconds required for the $i$-th student to reach school (i.e., the shortest distance in meters from node $h_i$ to node $s$).

sample

4 4 1
1 2 5
2 3 5
3 4 5
1 4 20
3
1
2
4

0
5
15