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:
ai, bi, ci
It means that the graph being described contains an edge from ai to bi, with a weight of ci.
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

Added by:Robert Rychcicki
Date:2009-01-10
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ERL JS-RHINO NODEJS OBJC PERL6 VB.NET

hide comments
2014-09-29 22:04:07 Neeraj
Breaking from loop on finding target node costed me 4 WA's. Print result after all the distances are calculated. Still dont know the reason why ?
2014-07-17 21:11:03 Luv Karakoti
A small mistake and SIGABRT for some 2 days :D Feeling so lucky after solving this question
2014-07-11 18:39:32 fanatique


Last edit: 2014-07-11 18:44:36
2014-07-04 08:50:06 anil
pls check sigkill error my sub id 11885287
2014-07-03 09:27:39 Kishlay Raj
is the number of nodes in the test cases more than 1000 too


Last edit: 2014-07-03 09:27:52
2014-05-25 09:07:14 tranquil
it is a directed graph....costed me 2 WA's
2014-05-23 12:03:38 kelaseek
no need of anything .. just dijkstra
2014-03-16 21:58:10 anti_tourist
Please provide any tricky test case ???

Last edit: 2014-03-16 22:17:26
2013-11-12 20:15:46 Rana Saha
weak test cases!
2013-10-27 17:48:13 Geanyous
get AC for first submission with SPFA lol
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.