Distance between vertices

Input

First line contains two integers $n$ and $m$ (n \leq 1000, m \leq 10000) - the number of vertices and edges in the graph correspondingly. Second line contains positive integers $s$ and $t$ (s, t \leq n, s \neq t) - the numbers of the vertices between which you need to find the weight of the minimum path. Next $m$ lines contain the description of edges, one edge in a line. The edge number $i$ is described with three positive integers b_i, e_i and w_i - the numbers of vertices connected by the edge and the edge weight (b_i, e_i \leq n, 0 \leq w_i \leq 10^5). It is guaranteed that the path between $s$ and $t$ exists.

Output

Print one number - the weight of the minimum path between the vertices $s$ and $t$.

Examples