Задачи
Расстояние между вершинами
Расстояние между вершинами
Дан неориентированный взвешенный граф. Найти вес минимального пути между двумя вершинами.
Входные данные
Первая строка содержит натуральные числа n, m, s и f\:(n \le 5000, m \le 10^5, 1 \le s, f \le n, s \neq f) - количество вершин и ребер графа а также номера вершин, длину пути между которыми требуется найти.
Следующие m строк содержат по три натуральных числа b_i, e_i и w_i — номера концов i-ого ребра и его вес соответственно (1 \le b_i, e_i \le n, 0 \le w_i \le 10^5).
Выходные данные
Первая строка должна содержать вес минимального пути между вершинами s и f. Во второй строке через пробел выведите вершины на кратчайшем пути из s в f в порядке обхода. Если путь из s в f не существует, выведите -1.

Пример
Входные данные #1
4 4 1 3 1 2 1 2 3 2 3 4 5 4 1 4
Выходные данные #1
3 1 2 3