ADRABR  Adrita and Her Bike Ride
Adrita, a lady Programmer is at Uttara, at her office. She needs to go home now. But she forgot to take enough money with her. She has limited money, so she can’t afford Uber Ride. She called her friend to give a ride on her bike. But Adrita wants to pay her friend and she wants minimum cost shortest path to reach to her home.
There are several points and there are roads connecting the points. All connecting roads are of length of 1 kilometer. Some roads (like flyover) will charge tolls and the tolls are given. You are to find the shortest path based on minimal cost.
Consider the cost for 1 kilometer is 12 taka for bike ride.
Input
In the first line of input, there’s a positive integer k (k <= 50) denoting the number of test cases.
In each test case, the first line contains 4 integers N (1 <= N <= 10^5) denoting the number of points, R (1<=R<= 10^6) denoting the number of connecting roads, S (1 <= S <= N) denoting the starting point, D (1 <= D <= N) denoting the destination point.
The next R lines contains 3 integers each, U, V (1 <= U, V <= N) and T, (0 <=T <= 10^5) indicating that point U and V are connected with the road which requires toll T taka. All roads are bidirectional and you can assume that the destination point is reachable from the starting point.
Output
Print the minimum cost to reach her destination.
Example
Input
1 6 6 1 6 1 2 0 2 3 0 3 4 1 4 5 2 5 6 0 4 6 12
Output
61
hide comments
sarwar_h:
20180120 20:49:12
@amulyagaur, problem statement is updated. 

pvsmpraveen:
20180115 06:49:12
T >= 0 and T<=10^5


shubham_001:
20180105 14:53:53
@amulyagaur yes I wanna know that too!


amulyagaur:
20180101 07:50:25
constraints on T ?? (lower bound) 
Added by:  Sarwar 
Date:  20171230 
Time limit:  1s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All 