Problems
Distance between vertices
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 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.
Input example #1
4 4 1 3 1 2 1 2 3 2 3 4 5 4 1 4
Output example #1
3