e-olymp
Competitions

ADA University - February 3 - Dijkstra

Distance betweeen the vertices

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

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

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

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

___________________________________________

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

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

Input

First line contains two numbers n and m (1n100000, 1m200000) - 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.

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