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

# 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`, `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.

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