dinesh-and-his-travelling-cost

Dinesh has been appointed as a Civil engineer of Jamshedpur city. He has selected some locations in the city for the road construction.
For simplicity he numbered those locations as 0,1,2,3,....500. He constructed roads between various pairs of location(say A and B ) and with the permission from the government,fixed the cost for travelling between those pair of locations from either end as W unit.

After completion of his project he  wants to find the minimum cost for travelling from location U (source) to Q number of other locations (destination).

Input

First line contains N ,the number of roads that Dinesh constructed.

Next N line contains three integers A ,B, and W.

A and B represent the locations between which the road was constructed and W is the fixed cost for travelling from A to B or from B to A.

Next line contains a number U from where Dinesh wants to travel to other locations.

Next line contains Q , the number of queries (finding cost) that he wants to perform.

Next Q lines contain an integer V (destination) for which minimum cost is to be found from U.

Output

Print the required answer in each line.

Note :If he can't travel from location U to V by any means then, print "NO PATH" without quotes.

Constraints:

1 ≤ N ≤ 500

0 ≤ A,B ≤ 500

1 ≤ W ≤ 100

0 ≤ U,V ≤ 500

1 ≤ Q ≤ 500

SAMPLE INPUT
7
0 1 4
0 3 8
1 4 1
1 2 2
4 2 3
2 5 3
3 4 2
0
4
1
4
5
7

SAMPLE OUTPUT
4
5
9
NO PATH

Explanation

Query #1

0->1: cost =4

Query #2

0->4= 0->1->4 cost=4+1=5

Query #3

0->5= 0->1->2->5 cost=4+2+3=9

Query #4

0->7= no path exist between 0 and 7

Source: hackerearth | Difficulty: UNKNOWN_DIFFICULTY


Solutions: