TRVCOST  Travelling cost
The government of Spoj_land has selected 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
hide comments
shahi9935:
20180616 16:50:28
Thanks @sherlock11. Your warning was of great help. 

sherlock11:
20180608 13:11:24
input contains same edges more than once..........so take care of that 

ameyanator:
20180330 18:54:01
It appears that the test cases are weak. My Floyd Warshall algo was giving the wrong answer but still it ran correctly. Also a huge running time gap between floyd warshall and dijkstra! 

nadstratosfer:
20180217 04:44:22
Constraints are stated correctly, got AC assuming U,V <= 500. Read older comments for WArelated hints. Good problem. 

ztoa1:
20170828 05:12:24
Those getting error in test case 10,check for :


anubhav1772:
20170724 19:03:40
AC in 1 GO :) 

ankitshrey112:
20170705 22:40:35
If you are getting wrong answer at test case 10 , then consider it is an undirected graph. 

vaibhavk31:
20170621 22:55:50
With djikstras AC


akshay_agarwal:
20170610 20:59:28
getting wa on test 10 again and again , even made the array of size 1100. Please help. Last edit: 20170610 21:00:04 

komninos:
20170429 16:47:18
Last edit: 20170429 16:48:18 
Added by:  ivar.raknahs 
Date:  20150305 
Time limit:  0.5s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ASM64 JSMONKEY 
Resource:  own 