ADRABR - Adrita and Her Bike Ride

女程序员 Adrita 在 Uttara 的办公室里。 她现在需要回家。 但是她忘了带走足够的钱。 她的资金有限，因此无法负担 Uber Ride。 她打电话给朋友骑自行车。 但是阿德里塔（Adrita）想付钱给她的朋友，而且她希望以最低的费用以最短的途径到达她的家。 有几个点，有连接这些点的道路。 所有连接道路的长度均为 1 公里。 有些道路（如天桥）将收取通行费，并给出了通行费。 您将基于最小的成本找到最短的路径。 考虑到骑自行车 1 公里的成本是 12 塔卡。 ### 输入格式 在输入的第一行中，有一个正整数 $k(k <= 50)$ 表示测试用例的数量。 在每个测试案例中，第一行包含 $4$ 个整数 $N(1 <= N <= 10^5)$ 表示点数 $R(1 <= R <= 10^6)$ 表示连接道路数 $S(1 <= S <= N)$ 表示起点，$D(1 <= D <= N)$ 表示终点。 接下来的 $R$ 条线分别包含 $3$ 个整数，$U,V(1 <= U，V <= N)$ 和 $T(0 <= T <= 10^5)$，指示 $U$ 和 $V$ 点与需要连接的道路相连 收费塔卡。 所有道路都是双向的，您可以假设从起点可以到达目的地。

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.

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.

Print the minimum cost to reach her destination.

1

6 6 1 6
1 2 0
2 3 0
3 4 1
4 5 2
5 6 0
4 6 12

61