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

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

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

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

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