e-olymp
favorite Нам необхідно трохи Вашої допомоги щоб сайт продовжував працювати, натисніть на банер щоб дізнатись більше.
Змагання

Dijkstra algorithm

Расстояние между вершинами

Дан взвешенный граф. Требуется найти вес минимального пути между двумя вершинами.

Входные данные

Первая строка содержит два натуральных числа n и m (n1000, m10000) - количество вершин и ребер графа соответственно. Вторая строка содержит натуральные числа s и t (s, tn, s <> t) - номера вершин, длину пути между которыми требуется найти. Следующие m строк содержат описание ребер по одному на строке. Ребро номер i описывается тремя натуральными числами bi, ei и wi - номера концов ребра и его вес соответственно (bi, ein, 0wi105). Гарантируется, что существует путь из s в t.

Выходные данные

Вывести одно натуральное число - вес минимального пути между вершинами s и t.

Ліміт часу 1 секунда
Ліміт використання пам'яті 128 MiB
Вхідні дані #1
4 4
1 3
1 2 1
2 3 2
3 4 5
4 1 4
Вихідні дані #1
3
Джерело 2018 Azerbaijan School Competition, II Stage, April 8, Problem A