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
selva1996:
20180611 21:54:01
Use Struct instead of Pair...for me using Pair was giving me time out.... Last edit: 20180611 21:54:33 

ameyanator:
20180425 08:46:20
My dijkstra with multiset runs in 0.04 secs. But how to solve with MST? 

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

sunny:
20170814 21:53:49
AC in one Go :). Dijkstra's. 

marwankhaled:
20170801 18:34:31
My 50th :D


indra_5672:
20170703 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 

rohit9934:
20170614 19:54:37
AC in a go using Dijkstra.


code_aim:
20170525 20:17:48
very weak test cases!! 

testing java:
20170114 14:24:48
@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.


flyingduchman_:
20161229 17:35:13
Dijkstra with priorityqueue of STL ac .04s 
Added by:  Daniel Gómez Didier 
Date:  20081118 
Time limit:  0.516s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ERL JSRHINO NODEJS PERL6 VB.NET 
Resource:  Circuito de Maratones ACIS / REDIS 