e-olymp
Competitions

ADA University - February 3 - Dijkstra

Distance between vertices

The weighted 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