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
sujit yadav: 2015-09-18 23:26:30

mst is not dijsktra ... wrong tag :p

moovon: 2015-08-23 07:30:30

dijsktra is fine enough

shuks: 2015-07-30 18:08:34

STL <3

Tim Wargon: 2015-05-15 21:43:18

NO...Dijkstra without prior. queue works fine too.

Last edit: 2015-05-16 09:47:31
sai krishna: 2015-03-08 06:04:11

ha ha ha AC :)

Hahaha: 2014-12-03 18:52:41

Simple dijsktra with prioirty queue will pass very easily

Varun Gambhir: 2014-08-30 13:21:02

Simple dijikstra will work fine

Ayur Jain: 2014-06-27 13:31:33

Dijsktra via priority queue is fast enough

Itachi: 2014-06-25 13:22:51

int is enough. ll gave a TLE.

Sujith Konanki: 2014-03-22 20:32:13

http://ideone.com/JKTQW0 working in ideonw but giving SGVABRT help


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