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