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** (**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`

and _{i}`w`

- the numbers of vertices connected by the edge and the edge weight (_{i}`b`

, _{i}`e`

≤ _{i}**n**, **0** ≤ `w`

≤ _{i}`10`

). It is guaranteed that the path between ^{5}**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