eolymp
Соревнования

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

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

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

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

Первая строка содержит два натуральных числа n и m (n1000, m10000) - количество вершин и ребер графа соответственно. Вторая строка содержит натуральные числа s и t (s, tn, st) - номера вершин, длину пути между которыми требуется найти. Следующие 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