e-olymp
favorite We need a little bit of your help to keep things running, click on this banner to learn more
Competitions

Dijkstra algorithm

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 (n1000, m10000) - the number of vertices and edges in the graph correspondingly. Second line contains positive integers s and t (s, tn, st) - 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, ein, 0wi105). 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.

Time limit 1 second
Memory limit 128 MiB
Input example #1
4 4
1 3
1 2 1
2 3 2
3 4 5
4 1 4
Output example #1
3
Source 2018 Azerbaijan School Competition, II Stage, April 8, Problem A