Input

The first line of each test case contain two integers N and M (3 ≤ N ≤ 1000, M ≥ 0), indicating the number of cities and the number of roads. The next line contain two numbers S and T (S ≠ T), indicating the start point and the destination. Each line of the following M lines contain three numbers A_i, B_i and C_i (1 ≤ A_i,B_i ≤ N, 1 ≤ C_i ≤ 1000), indicating that there is a road between city A_i and city B_i, whose length is C_i. Please note all the cities are numbered from 1 to N.

The roads are undirected, that is, if there is a road between A and B, you can travel from A to B and also from B to A.

Output

Sample Input

2
3 3
1 3
1 2 10
2 3 20
1 3 50
3 1
1 3
1 2 10

Sample Output

30
-1