There are N places and M bidirectional way. No two places have more than one direct way. Ana wants to walk from S to T and return to S by a itinerary that satisfy:

-          No way can be go twice.

-          Length of itinerary is the minimum.

Input

Line 1: 4 integers: N, M, S, T (N <= 10⁴; M <= 10⁵)

Next M line: Line i include 3 integers u_i, v_i, c_i: distance of two places u_i and v_i is c_i. (c_i <= 2000000000).

Output

Length of the itinerary if it exists. Else print -1.

Example

Input:
5 7 1 5
1 2 3
1 4 8
2 3 5
2 4 4
3 5 5
4 3 8
4 5 3

Output:
24