HIGHWAYS - Highways

A number of cities are connected by a network of highways. Each highway is bidirectional and connects two cities, with a given travel time. What is the shortest time to get from a given city to another given city?

Input

The first line of input contains the number of test cases.

Each test case starts with a line containing the number of cities n (2 ≤ n ≤ 100000), the number of highways m (1 ≤ m ≤ 100000), the starting city and the ending city. Cities are numbered from 1 to n.

Then m lines follow, each describing one highway. The description consists of the two distinct city numbers and the time in minutes to travel along the highway. The time will be between 1 and 1000.

Output

For each test case output a single line containing the minimum time it takes to get from the start to the destination. If no connection exists, output NONE.

Example

Input:
2
4 2 1 4
1 2 5
3 4 5
4 4 1 4
1 2 5
2 3 5
3 4 5
4 2 6

Output:
NONE
11

Added by:Daniel Gómez Didier
Date:2008-11-18
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ERL JS-RHINO NODEJS PERL6 VB.NET
Resource:Circuito de Maratones ACIS / REDIS

hide comments
2018-04-25 08:46:20
My dijkstra with multiset runs in 0.04 secs. But how to solve with MST?
2017-10-20 21:38:58
Why my solution is not getting accepted. I mean , after clicking submit button ,it's not running.:(
2017-08-14 21:53:49 sunny
AC in one Go :-). Dijkstra's.
2017-08-01 18:34:31
My 50th :D
First dijkstra
2017-07-03 09:34:35
I solved it using dijkstra but i think we can solve it using mst because after finding mst we can find path between given nodes if it exists then it will be minimum time path. tell me if i am wrong @rohit9934 @admin @ nsitsk
2017-06-14 19:54:37
AC in a go using Dijkstra.
How to do it with Minimum Spanning tree. Please help
2017-05-25 20:17:48
very weak test cases!!
2017-01-14 14:24:48 testing java
@pd42slok as far as I know, you can't solve shortest path problem using an MST algorithm (such as kruskal). If i'm wrong, please feel free to enligh me. Otherwise, @admin - please correct the tag.

=(Francky)=> EB members are not responsible of the tags... They are posted by some psolvers, and can be sometimes spoil or wrong assert. You can choose option 'do not display tags' with your account.
Maybe one day, tag will be set by EB only, ...

Last edit: 2017-01-14 16:48:58
2016-12-29 17:35:13
Dijkstra with priority-queue of STL ac .04s
2016-11-29 07:41:17 lt
Dijkstra rocks. Done using sets!
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.