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

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

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

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

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

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

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

Примеры