eolymp
bolt
Попробуйте наш новый интерфейс для отправки задач
Задачи

Алгоритм Йена

Алгоритм Йена

Лимит времени 1 секунда
Лимит использования памяти 128 MiB

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

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

В первой строке содержатся количество вершин n (1n100) и рёбер m (1m4000) в графе, а также порядковый номер пути k (1k500). В следующих строках описываются рёбра графа - тройка (u, v, w) описывает ребро, соединяющее вершины u и v весом w. В последней строке содержатся номера двух вершин s и t, между которыми требуется искать путь.

В графе не может быть кратных рёбер, не может быть петель. Все веса положительны и не превышают 10000. Гарантируется, что искомый путь существует.

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

В первой строке выведите два числа - искомый вес пути и число вершин в нём. В следующей строке выведите сам путь - последовательность номеров вершин.

Пример

Входные данные #1
5 10 3
1 2 6
1 3 13
1 4 18
1 5 35
2 3 14
2 4 34
2 5 17
3 4 22
3 5 15
4 5 34
1 5
Выходные данные #1
35 2
1 5