One day, Little Sub who lives in the city S decides to visit AA who lives in the city T .

Little Sub lives in a country consists of N cities and M bidirectional roads. However, one of the roads is currently under construction and no one can pass the road. Little Sub doesn’t know which road it is and he can know whether a road is under construction only when he is in either city connected by the road.

Please help Little Sub minimize the total length of the route in the worst case. You don’t need to decide a route in advance of departure and you can choose where to go next at any time. If Little Sub cannot reach the city T in the worst case, output −1.

The first line contains four integers N,M,S,T(2 ≤ N ≤ 10^5,1 ≤ M ≤ 2∗10^5,1 ≤ S,T ≤ N,S != T).

The following M lines represent road information: the ith line of the M lines consists of three integers ui, vi, ci which means the ith road connects the cities ui and vi(1 ≤ ui, vi ≤ N, ui != vi) with the length ci(1 ≤ ci ≤ 10^9). It is guaranteed that there are no multiple-edges and self-loops.

It is also promised that all the pairs of the cities are connected if no road is under construction.

Output the minimum total length of the route in the worst case. If you cannot reach the city T in the worst case, output −1.