e-olymp
Məsələlər

Кратчайший путь

Кратчайший путь

Дан неориентированный взвешенный граф. Найти кратчайший путь между двумя данными вершинами.

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

Первая строка содержит натуральные числа n и m (n2000, m50000) - количество вершин и рёбер графа. Вторая строка содержит натуральные числа s и f (1s, fn, sf) - номера вершин, длину пути между которыми требуется найти. Следующие m строк содержат по три числа bi, ei и wi - номера концов i-ого ребра и его вес соответственно (1bi, ein, 0wi100000).

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

Первая строка должна содержать одно число - длину минимального пути между вершинами s и f. Во второй строке через пробел выведите вершины на кратчайшем пути из s в f в порядке обхода. Если путь из s в f не существует, выведите -1.

Zaman məhdudiyyəti 2 saniyə
Yaddaşı istafadə məhdudiyyəti 128 MiB
Giriş verilənləri #1
4 4
1 3
1 2 1
2 3 2
3 4 5
4 1 4
Çıxış verilənləri #1
3
1 2 3