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

Вхідні дані

У першому рядку міститься кількість вершин $n$ (1 \leq n \leq 100), кількість ребер $m$ (1 \leq m \leq 4000) у графі, а також порядковий номер шляху $k$ (1 \leq k \leq 500).

У наступних $m$ рядках описано ребра графа. Кожен рядок містить трійку (u, v, w), яка описує ребро, що з'єднує вершини $u$ та $v$ з вагою $w$.

У останньому рядку містяться номери двох вершин $s$ та $t$, між якими потрібно знаходити шлях.

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

Вихідні дані

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

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

Приклади