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

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

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

Первая строка содержит два натуральных числа n и m (n ≤ 1000, m ≤ 10000) - количество вершин и ребер графа соответственно. Вторая строка содержит натуральные числа s и t (s, t ≤ n, s ≠ t) - номера вершин, длину пути между которыми требуется найти. Следующие m строк содержат описание ребер по одному на строке. Ребро номер i описывается тремя натуральными числами b[i], e[i] и w[i] - номера концов ребра и его вес соответственно (b[i], e[i] ≤ n, 0 ≤ w[i] ≤ 10^5). Гарантируется, что существует путь из s в t.

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

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

Примеры