e-olymp
favorite Нам необходимо немного Вашей помощи чтобы сайт продолжал работать, нажмите на банер чтобы узнать больше.

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

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

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

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