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
Samer: 2014-02-25 13:40:07

dijkstra <3 <3 <3

vishnu: 2014-02-14 10:42:35

dijikstra works fine for me :)

Abhishek Gupta: 2014-02-07 13:25:06

dijkstra is slow (1.29sec)...
any faster algo???

Abhimanyu: 2013-12-19 20:58:29

int works fine :)

Python: 2013-10-17 06:33:56

does the test cases end with EOF
EDIT:- AC :D
if first input is

Last edit: 2013-10-17 06:35:13
Prakash: 2013-08-02 04:55:29

getting TLE, used O(ElogV) for dijkstra! Help

srikardurgi: 2012-10-15 16:27:55


forget about the mentioned range and use long long int for all variables

Simón Murillo Gómez: 2012-08-20 01:33:46

Nothing special here. Just take care about the constraints

Last edit: 2012-08-20 01:53:28
张翼德: 2012-04-17 14:03:01

My program is working fine on ideone...but giving SGVABRT here on spoj....==><snip>

Last edit: 2023-02-22 20:28:38

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