The Chinese people threw themselves into an all-out war of resistance against Japanese aggression in 1937. The first line of  resistance against  aggression was formed by spies and underground workers.  

They lurked  in every place of the city.

There's a piece of information that needs to be passed on to them.  Now there is a  traffic map, each road connects two different intersections Xi and Yi, each of which is the termination for at least two road. The length of each road is known LENi,  no two intersections are directly connected by two different roads.

N spies lurk at every intersection , some intersections mignt have more than one spy. For security, they must position themselves properly , each spy cannot accept information from local intersection ,  can only be transferred from elsewhere and end up at the finishing pace.

At first, the information is in the hands of a spy at S intersection. After N spies transmission, and finally arrived at E intersection .

Write a program to find the shortest path that connects the starting intersection(S) and the ending intersection(E) ang transmission exactly N spies.

The first line of the input contains one integers T, which is the nember of  test cases (1<=T<=5).  Each test case specifies:

* Line 1:        Four space-separated integers:  N  M  S  E

* Lines 2..M+1:  Line i+1 describes road i with three space-separated integers:  LENi  Xi  Yi

          (  2<=N<=300,000  2<=M<=100,  1<= LENi, Xi, Yi ,S, E <=1000  i=1,…,m)

For each test case generate a single line containing a single integer that is the shortest path from intersection S to intersection E that transmits exactly N spies.

河南省第十届ACM竞赛