eolymp
Змагання

Алгоритм Дейкстри

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

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

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

Первая строка содержит два натуральных числа 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