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

hide comments
rishi_devan: 2016-08-21 19:48:16

Straight-forward Dijkstra's algorithm

pd42slok: 2016-08-20 21:09:26

can be solved by kruskal, so mst tag

nsitsk: 2016-07-08 20:18:11

@admin, Please correct the tag. This question is on dijkstra. Not MST.

iharsh234: 2016-07-08 12:47:39

stl rocks!!

distort: 2016-06-10 05:33:11

Only accepted in python 3.4!!
If using python 3.4 use heappop, heappush dont use priority queue

vijay kumar paliwal: 2016-06-03 14:11:50

Learnt Dijkstra with priority queue.. first problem solved using priority queue!
Made my day :)

Ray Brish Bhanu: 2016-04-15 11:22:29

for edges take structure not pair..caused me several tle

vedang: 2015-12-05 21:03:34

Not MST, but Dijkstra!

kartikay singh: 2015-10-19 15:27:59

Djikstra + priority_queues
AC 0.05s

Last edit: 2015-10-19 15:28:23
sarvagya: 2015-09-26 00:11:35

Djikstra with sets -> 0.05s
with priority_queue -> 0.04s
priority_queues are faster .


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