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 bi, ei and wi - the numbers of vertices connected by the edge and the edge weight (bi, ei ≤ n, 0 ≤ wi ≤ 105). 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.