The city is in the form of a graph and there are N junctions that are connected by M bidirectional roads. The time taken to travel on the ith road is ti. Your house is located at the junction with index s, whereas your storeroom is at junction d. There are several chocolate shops in the city. In the case of any chocolate shortage, shop workers are dispatched from all the police stations immediately.
You are required to determine the least amount of time in which you can reach the storerooms after coming from your house without being intercepted by any staff of chocolate shops at any junction of the city.
Note: Workers can only intercept you at any of the junctions in the city.
Input format
Output format
For each test case, print a single integer denoting the least amount of time in which you can reach your storeroom avoiding the shop workers. If no such path exists, then print −1.
Constraints
1≤T≤10
1≤N,M≤105
1≤s,d≤N
1≤u,v≤N
1≤t≤109
In the first test case, junctions 1 and 4 have police stations.
MGM Grand is at 2 and safe house at junction 3.
After committing the crime, Danny can reach the safehouse from junction 2 in 3 units of time without being intercepted by the police at any of the junctions.
In the second test case, junction 2 has a police station.
MGM Grand is at junction 2 and safehouse at 1.
Since the police station is at the same junction as MGM Grand police will intercept Danny immediately. Hence, −1.