EZDIJKST  Easy Dijkstra Problem
Determine the shortest path between the specified vertices in the graph given in the input data.
Hint: You can use Dijkstra's algorithm.
Hint 2: if you're a lazy C++ programmer, you can use set and cin/cout (with sync_with_stdio(0))  it should suffice.
Input
first line  one integer  number of test cases
For each test case the numbers V, K (number of vertices, number of edges) are given,
Then K lines follow, each containing the following numbers separated by a single space:
a_{i}, b_{i}, c_{i}
It means that the graph being described contains an edge from a_{i} to b_{i},
with a weight of c_{i}.
Below the graph description a line containing a pair of integers A, B is present.
The goal is to find the shortest path from vertex A to vertex B.
All numbers in the input data are integers in the range 0..10000.
Output
For each test case your program should output (in a separate line) a single number C  the length of the shortest path from vertex A to vertex B. In case there is no such path, your program should output a single word "NO" (without quotes)
Example
Input: 3 3 2 1 2 5 2 3 7 1 3 3 3 1 2 4 1 3 7 2 3 1 1 3 3 1 1 2 4 1 3 Output: 12 5 NO
hide comments
abhishek18620:
20170215 23:16:25
nodes r definitely more than 1000..so dont hardcode it for 1000. 

aliosm:
20161223 19:03:16
AC first GO! 

tregiengchan:
20161216 10:57:40
Accept with C++ (g++ 14), but not C++ (g++ 3.4.2) 

square1001:
20160806 11:58:58
I got AC after 2 internal errors... 

shubh809:
20160805 16:21:19
Last edit: 20161110 12:27:28 

akhileshsoni96:
20160718 22:29:22
please submit in C++(g++ 14) got A.C :)


coderaashir:
20160712 19:00:10
No need for long long, and I got AC while using cin/cout without sync_with_stdio(0)


surya97:
20160510 07:16:21
Solved in 0.18s in Java. Costed 1 WA for using undirected graph. 

bruzelee:
20160503 23:43:40
Given graph is directed !!! 

ankushbbbr:
20160405 19:19:28
getting a wrong answer with java 
Added by:  Robert Rychcicki 
Date:  20090110 
Time limit:  0.150s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ERL JSRHINO NODEJS OBJC PERL6 VB.NET 