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

Added by:Sarwar
Date:2017-12-30
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All

hide comments
2020-07-28 07:55:27
Ac in 1st go. Pretty easy problem
2020-06-26 14:59:30
Roads are bi-directional.
Cost me 10 min of debugging and 3 WA.
2020-03-04 05:49:25
Beware of graph containing duplicated edges with different costs.
2019-12-19 17:19:36
Thanks @problem setter, learnt a new thing today ;)
2019-01-11 21:07:30
Just can not figure out why getting WA even with correct Djikstra implementation and long long
2018-06-28 20:57:23
Can anyone provide a test case as I am continuously getting WA!!
2018-01-20 20:49:12
@amulyagaur, problem statement is updated.
2018-01-15 06:49:12
T >= 0 and T<=10^5
and ints will give wa.
2018-01-05 14:53:53
@amulyagaur yes I wanna know that too!
2018-01-01 07:50:25
constraints on T ?? (lower bound)
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.