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
ort: 2018-11-16 15:25:46

Nothing special here, just dijkstra...

joqsan_77: 2018-08-04 19:48:56

MST doesn't work here.

paroaro: 2018-07-19 17:31:14

ez ternaryserch

karan_yadav: 2018-07-11 19:44:09

@indra Generally speaking MST is the minimum cost involved in connecting all the nodes of a graph. It doesn't guarantee that given path between two nodes is of minimum cost.
ie let's say we have a graph with 3 nodes - A, B, C.
A-B cost is 10
B-C cost is 4
C-A cost is 8
Note - All paths are bidirectional
Minimum Spanning Tree will be A-C-B as this will give a total cost of 8 + 4 = 12 as compare to A-B-C (cost 14) and B-A-C (cost 18). According to you the least cost between A and B will be the cost from MST (A-C-B) which is 12 (you'll traverse A-C then C-B -> total cost 12) but actually, A-B min cost is 10.
Hope it helps.

Last edit: 2018-07-26 10:56:08
ankit1cool: 2018-06-20 20:00:56

use dijkstra's and break as soon as destination is found

selva1996: 2018-06-11 21:54:01

Use Struct instead of Pair...for me using Pair was giving me time out....

Last edit: 2018-06-11 21:54:33
ameyanator: 2018-04-25 08:46:20

My dijkstra with multiset runs in 0.04 secs. But how to solve with MST?

nilesh8757: 2017-10-20 21:38:58

Why my solution is not getting accepted. I mean , after clicking submit button ,it's not running.:(

sunny: 2017-08-14 21:53:49

AC in one Go :-). Dijkstra's.

marwankhaled: 2017-08-01 18:34:31

My 50th :D
First dijkstra


Added by:Daniel Gómez Didier
Date:2008-11-18
Time limit:0.516s
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