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
sarthak_19: 2020-07-09 13:43:03

Dijkstra with set works fine

nathanaxel: 2020-04-01 04:25:07

why do ikeep getting TLE ::"(

purplecs: 2019-11-13 17:13:35


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

jnu_siddharth: 2019-04-02 08:19:52

Good Problem to apply Dijkstra.
But everyone should try the MST also.

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

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