Distance between vertices

The weighted undirected graph is given. Find the weight of the minimum path between two vertices.

Input

First line contains two integers n and m (n ≤ 1000, m ≤ 10000) - the number of vertices and edges in the graph correspondingly. Second line contains positive integers s and t (s, t ≤ n, s ≠ t) - the numbers of the vertices, the length between which you must find. Next m lines contain the description of edges, one edge in a line. The edge number i is described with thee 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] ≤ n, 0 ≤ w[i] ≤ 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