TRVCOST - Travelling cost

The government of Spoj_land has selected a number of locations in the city for road construction and numbered those locations as 0, 1, 2, 3, ... 500.

Now, they want to construct roads between various pairs of location (say A and B) and have fixed the cost for travelling between those pair of locations from either end as W unit.

Now, Rohit being a curious boy 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 government 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 an integer U from where Rohit wants to travel to other locations.

Next line contain 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.

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

Example

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

Output:
4
5
9
NO PATH

Constraints

1 <= N <= 500

0 <= A, B <= 500

1 <= W <= 100

0 <= U, V <= 500

1 <= Q <= 500

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


Added by:ivar.raknahs
Date:2015-03-05
Time limit:0.5s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64 JS-MONKEY
Resource:own

hide comments
2017-01-09 12:20:43 Shubhojeet Chakraborty
For people getting WA on test 10,looks like the destination node can be greater than 500.Just changed the constraint from 505 to 1050 and got AC.

Last edit: 2017-01-09 12:21:02
2016-08-17 19:46:50 Gaurav Dahima
straight forward Dijkstra :D
2016-08-11 19:46:11
easy one..
accepted in 0.00 :)
2016-08-09 09:06:42
Small constraints make it easy!!
2016-07-29 08:40:59
i am getting WA at 10th test case. Don't know whats wrong .Please have a look, my solution id is 17389481.
2016-07-11 12:15:53
Simply implement Dijkstra's algorithm. Easy!!!
Ac in 1 go... ^_^
2016-06-29 20:36:30
Input can be formatted in any style (dont assume 3 numbers on same line)
Edges may repeat (make sure to take the least one)
Make sure o/p is NO PATH if source doesnt exist
<<*********************************************>>

Last edit: 2016-06-29 20:47:08
2016-06-12 07:14:14
Problem with the compiler getting SIGSEV though my code is right
Code id:17093449
2016-05-10 07:38:26
undirected graph
2016-04-01 21:15:22
getting wrong answer.....test case runs fine, checked for all possible logical errors mentioned earlier in comments
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.