SPOJ Problem Set (classical) 3381. Highways Problem code: 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 decription 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

---

Added by:	Daniel Gómez Didier
Date:	2008-11-18
Time limit:	3s
Source limit:	50000B
Languages:	All except: CLOJ ERL F# JS PERL 6 TECS
Resource:	Circuito de Maratones ACIS / REDIS