P17729 [HackerEarth] Dinesh has been appointed as a Civil engineer of Jamshedpur city. He has selected some locations in the city for the road construction.
普及
题目描述

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

输入格式

见题面

输出格式

见题面

样例输入
20 1 10 10 1 2 10 1 7 34 1 23 90 1 45 20 1 4 30 1 23 20 1 67 34 1 78 34 1 89 23 1 43 56 1 78 23 1 43 10 1 92 90 1 71 65 1 73 29 1 78 90 1 79 83 1 99 99 1 100 100 1 20 34 56 34 23 57 100 13 24 56 7 45 65 49 87 65 43 89 87 61 60
样例输出
3 NO PATH NO PATH NO PATH NO PATH NO PATH NO PATH NO PATH NO PATH NO PATH NO PATH NO PATH NO PATH NO PATH 3 NO PATH NO PATH NO PATH NO PATH 514 NO PATH NO PATH NO PATH NO PATH NO PATH NO PATH NO PATH NO PATH NO PATH NO PATH NO PATH NO PATH NO PATH NO PATH NO PATH NO PATH NO PATH NO PATH NO PATH NO PATH NO PATH NO PATH NO PATH NO PATH NO PATH NO PATH NO PATH NO PATH NO PATH NO PATH NO PATH NO PATH NO PATH 59 NO PATH NO PATH NO PATH NO PATH NO PATH NO PATH NO PATH NO PATH NO PATH NO PATH NO PATH NO PATH NO PATH NO PATH NO PATH NO PATH NO PATH NO PATH NO PATH NO PATH NO PATH NO PATH NO PATH NO PATH NO PATH NO PATH NO PATH NO PATH NO PATH NO PATH NO PATH NO PATH NO PATH NO PATH NO PATH NO PATH 3 NO PATH 313 NO PATH NO PATH NO PATH NO PATH NO PATH NO PATH NO PATH NO PATH NO PATH NO PATH NO PATH NO PATH NO PATH NO PATH NO PATH NO PATH NO PATH NO PATH NO PATH NO PATH NO PATH NO PATH NO PATH NO PATH NO PATH NO PATH NO PATH NO PATH NO PATH NO PATH NO PATH NO PATH NO PATH NO PATH NO PATH NO PATH NO PATH NO PATH NO PATH NO PATH NO PATH NO PATH NO PATH 160 NO PATH NO PATH NO PATH NO PATH NO PATH NO PATH NO PATH 160 NO PATH NO PATH NO PATH NO PATH NO PATH NO PATH NO PATH NO PATH 3 NO PATH NO PATH NO PATH NO PATH NO PATH NO PATH NO PATH NO PATH NO PATH NO PATH 230 NO PATH NO PATH NO PATH NO PATH NO PATH NO PATH NO PATH NO PATH NO PATH NO PATH NO PATH NO PATH NO PATH NO PATH NO PATH NO PATH NO PATH NO PATH NO PATH NO PATH NO PATH NO PATH NO PATH NO PATH NO PATH NO PATH NO PATH NO PATH NO PATH NO PATH NO PATH NO PATH NO PATH NO PATH NO PATH NO PATH NO PATH 160 NO PATH NO PATH NO PATH NO PATH NO PATH NO PATH NO PATH 3 NO PATH NO PATH NO PATH NO PATH 508 NO PATH NO PATH NO PATH NO PATH NO PATH NO PATH NO PATH NO PATH NO PATH NO PATH NO PATH NO PATH NO PATH NO PATH NO PATH NO PATH NO PATH NO PATH NO PATH NO PATH NO PATH NO PATH NO PATH NO PATH NO PATH NO PATH NO PATH NO PATH NO PATH NO PATH NO PATH 382 NO PATH NO PATH NO PATH NO PATH NO PATH NO PATH NO PATH NO PATH NO PATH NO PATH NO PATH NO PATH NO PATH NO PATH NO PATH NO PATH NO PATH NO PATH NO PATH NO PATH NO PATH NO PATH NO PATH NO PATH NO PATH NO PATH NO PATH NO PATH NO PATH NO PATH NO PATH NO PATH NO PATH NO PATH NO PATH NO PATH NO PATH NO PATH NO PATH NO PATH NO PATH NO PATH NO PATH 599 NO PATH NO PATH NO PATH NO PATH NO PATH NO PATH NO PATH NO PATH NO PATH NO PATH NO PATH NO PATH NO PATH NO PATH NO PATH NO PATH NO PATH NO PATH NO PATH NO PATH NO PATH NO PATH NO PATH NO PATH NO PATH NO PATH NO PATH NO PATH NO PATH NO PATH NO PATH NO PATH NO PATH NO PATH 157 NO PATH NO PATH NO PATH NO PATH NO PATH NO PATH NO PATH NO PATH NO PATH NO PATH NO PATH NO PATH NO PATH NO PATH NO PATH NO PATH NO PATH NO PATH NO PATH NO PATH NO PATH NO PATH NO PATH NO PATH NO PATH NO PATH NO PATH NO PATH NO PATH NO PATH NO PATH NO PATH NO PATH NO PATH NO PATH NO PATH NO PATH NO PATH NO PATH NO PATH NO PATH NO PATH NO PATH NO PATH NO PATH NO PATH NO PATH NO PATH NO PATH NO PATH NO PATH NO PATH NO PATH NO PATH NO PATH NO PATH NO PATH 230 NO PATH NO PATH NO PATH NO PATH NO PATH NO PATH NO PATH NO PATH 372 NO PATH NO PATH NO PATH NO PATH NO PATH NO PATH