Problem J
Locomotive Lunacy

You are very excited to spend time at home for the holidays this year, and booked a train ticket far in advance. Unfortunately, snow storms have caused your train home to be cancelled, and you were only given a single coupon in return! Now you have to navigate the train network to find your way home.

We are given a set of train stations $\{ 0, 1, \ldots , n-1\} $, and a set of connections between these train stations. Each such connection $(u, v)$ is directed from the station $u$ to the station $v$, and has a cost $c$ for the ticket. You start at station $s$, and are trying to get home to station $t$.

Your coupon takes any one connection and halves its cost, rounded down. That is, it takes a connection with cost $c$ and allows you to use it with cost $\lfloor c/2 \rfloor $.

Find the cheapest way from $s$ to $t$ while using at most one coupon.

Input

The first line of input has two integers $n\ (1 \leq n \leq 10^5)$ and $m\ (1 \leq m \leq 2 \cdot 10^5)$ where $n$ is the number of train stations and $m$ is the number of connections.

The second line of input has the two integers $s,t\ (0 \leq s,t \leq n-1)$.

The next $m$ lines of input each have three integers $u,v\ (0 \leq u,v \leq n-1)$, and $c\ (0 \leq c \leq 10^8)$ representing a connection from $u$ to $v$ with cost $c$.

Output

Output the cost of the cheapest way to travel from $s$ to $t$ which uses at most one coupon. If there is no way to travel from $s$ to $t$, then output $-1$.

3 3
0 2
0 1 2
1 2 2
0 2 4

2

6 9
0 5
0 1 4
0 2 2
2 1 0
2 4 4
1 3 2
1 4 3
3 4 3
3 5 6
4 5 2

5