Revenge of the Broken Door

The JAG Kingdom has $N$ cities and $M$ bidirectional roads. The $i$-th road $(u_i, v_i, c_i)$ connects city $u_i$ and city $v_i$ and has length $c_i$. One day you, a citizen of the JAG Kingdom, decide to travel from city $S$ to city $T$. You know that one road in the kingdom is currently under construction and cannot be passed, but you do not know which road it is. You can find out whether a road is under construction only while you are in one of the two cities that the road connects.

Minimize the total length of your route in the worst case. You do not have to fix a route before departure, and you may decide where to go next at any time. If you cannot reach city $T$ in the worst case, output -1.

The input consists of a single test case in the following format.

N M S T
u1 v1 c1
.
.
.
uM vM cM

The first line contains four integers $N$, $M$, $S$, and $T$: $N$ is the number of cities ($2 \le N \le 100{,}000$), $M$ is the number of bidirectional roads ($1 \le M \le 200{,}000$), $S$ is the city you start from ($1 \le S \le N$), and $T$ is the city you want to reach ($1 \le T \le N$, $S \ne T$). The following $M$ lines describe the roads. The $i$-th of these lines contains three integers $u_i$, $v_i$, and $c_i$, meaning that the $i$-th road connects city $u_i$ and city $v_i$ ($1 \le u_i, v_i \le N$, $u_i \ne v_i$) and has length $c_i$ ($1 \le c_i \le 10^9$). You may assume that every pair of cities is connected when no road is under construction. That is, for every pair of cities $x$ and $y$ there is at least one route from $x$ to $y$ using the given roads. It is also guaranteed that there are no multiple edges, that is, $\{u_i, v_i\} \ne \{u_j, v_j\}$ for all $1 \le i < j \le M$.

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