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

Distance betweeen the vertices

Distance betweeen the vertices

Коль Дейкстрý писать без кучи,

То тайм-лимит ты получишь...

А в совсем другой задаче

Юзай кучу Фибоначчи!

___________________________________________

Спектакль преподавателей ЛКШ.июль-2007

Undirected weighted graph is given. Find the weight of the minimal path between two vertices.

Input

The first line contains two numbers n and m (1n105, 1m2 * 105) - the number of vertices and edges. Second line contains two numbers s and t (1s, tn, st) - the numbers of the vertices the length between which you need to find.

Next m lines contain the description of the edges, one edge in a line. The edge number i is described with three integers bi, ei и wi (1bi, ein, 0wi100) - the vertices connected by the edge and its weight.

Output

Print the weight of the minimal path between the vertices s and t, or -1 if there is no such path.

prb625.gif

Time limit 4 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