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

Знайдіть k-ий найкоротший шлях між двома фіксованими вершинами у неорієнтовному графі.

Вхідні дані

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

У графі не може бути кратних ребер, не може бути петель. Усі ваги додатні і не перевищують 10000. Гарантиується, що шуканий шлях існує.

Вихідні дані

У першому рядку виведіть два числа - шугану васу шляху та число вершин у ньому. У наступному рядку виведіть сам шлях - послідовність номерів вершин.

Приклади