Distance betweeen the vertices

An undirected weighted graph is given. Find the length of the shortest path between two specified vertices.

Input

The first line contains two positive integers $n$ and $m(1\le n\le 10^5,1\le m\le 2\cdot 10^5)$ — the number of vertices and edges in the graph. The second line contains two positive integers $s$ and $t(1\le s,t\le n,s\ne t)$ — the numbers of the vertices between which you need to find the shortest path.

The following $m$ lines contain the descriptions of the edges. Each edge $i$ is described by three integers $b_i,e_i$, and $w_i(1\le b_i,e_i\le n,0\le w_i\le 100)$ — the numbers of the vertices it connects and its weight.

Output

Print the weight of the shortest path between vertices $s$ and $t$, or $-1$ if no such path exists.

Examples