Isaac ma dość codziennej podróży do biura tą samą najkrótszą trasą. Choć oszczędza czas, musi wciąż oglądać te same widoki. Nie może już znieść tak nudnego dojazdu.

Pewnego dnia postanowił poprawić sytuację. Codziennie zmieni trasę choć trochę. Nowy plan wygląda tak: pierwszego dnia używa najkrótszej trasy. Drugiego dnia używa drugiej najkrótszej, czyli najkrótszej poza tą z pierwszego dnia. Ogólnie, dnia $k$ wybiera $k$-tą najkrótszą trasę. Oczywiście należy unikać odwiedzania tego samego miejsca dwa razy na jednej trasie.

Pomóż Isaac, pisząc program wyznaczający jego trasę w $k$-tym dniu. Problem łatwo modeluje się w języku teorii grafów. Program powinien znaleźć $k$-tą najkrótszą ścieżkę w danym grafie skierowanym.

Wejście

Wejście zawiera wiele zestawów danych, każdy w następującym formacie.

$$\begin{array}{ccccc}n&m&k&a&b\\x_1&y_1&d_1&&\\x_2&y_2&d_2&&\\&\vdots&&&\\x_m&y_m&d_m&&\end{array}$$

Każdy element wejścia w zestawie jest nieujemną liczbą całkowitą. Dwa lub więcej elementów w jednym wierszu oddziela spacja.

$n$ to liczba wierzchołków grafu. Możesz założyć $2 \le n \le 50$. $m$ to liczba (skierowanych) krawędzi. $a$ jest wierzchołkiem początkowym, a $b$ docelowym. Oba należą do zakresu od $1$ do $n$ włącznie. Masz znaleźć $k$-tą najkrótszą ścieżkę z $a$ do $b$. Możesz założyć $1 \le k \le 200$ i $a \ne b$.

$i$-ta krawędź prowadzi z wierzchołka $x_i$ do $y_i$ i ma długość $d_i$ ($1 \le i \le m$). Zarówno $x_i$, jak i $y_i$ należą do zakresu od $1$ do $n$ włącznie, a $d_i$ od $1$ do $10000$ włącznie. Można przejść bezpośrednio z $x_i$ do $y_i$, lecz nie z $y_i$ do $x_i$, chyba że taka krawędź jest jawnie podana. Krawędź łącząca tę samą parę wierzchołków jest unikalna, jeśli istnieje: gdy $i \ne j$, nie zachodzą jednocześnie $x_i=x_j$ i $y_i=y_j$. Nie ma pętli, czyli $x_i$ nigdy nie jest równe $y_i$. Zatem $0 \le m \le n(n-1)$.

Podany graf może być bardzo nierealistyczną siecią drogową. Dane sędziowskie zawierają zarówno przypadki $m=0$, jak i $m=n(n-1)$.

Po ostatnim zestawie danych występuje wiersz z pięcioma zerami oddzielonymi spacjami.

Wyjście

Dla każdego zestawu wejściowego wypisz jeden wiersz zgodnie z poniższymi zasadami. Wiersz nie może zawierać dodatkowych znaków, takich jak spacje.

Jeżeli liczba różnych ścieżek z $a$ do $b$ jest mniejsza niż $k$, wypisz napis None. Pierwsza litera jest wielka, a pozostałe małe.

Jeżeli liczba różnych ścieżek z $a$ do $b$ wynosi co najmniej $k$, wypisz numery wierzchołków odwiedzanych na $k$-tej najkrótszej ścieżce, w kolejności odwiedzania, oddzielone łącznikiem (znakiem minus). $a$ musi być pierwsze, a $b$ ostatnie w wypisanym wierszu.

W tym zadaniu pojęcie „krótsza” (a więc także „najkrótsza”) ma szczególne znaczenie. Ścieżka $P$ jest krótsza od $Q$ wtedy i tylko wtedy, gdy zachodzi jeden z poniższych warunków.

1. Długość $P$ jest mniejsza niż długość $Q$. Długość ścieżki to suma długości jej krawędzi.

2. Długości $P$ i $Q$ są równe, a ciąg numerów wierzchołków $P$ jest wcześniejszy w porządku leksykograficznym niż ciąg $Q$. Dokładniej: oznaczmy ciąg $P$ przez $p_1,p_2,\ldots,p_s$, a ciąg $Q$ przez $q_1,q_2,\ldots,q_t$. Mamy $p_1=q_1=a$ i $p_s=q_t=b$. Ciąg $P$ jest wcześniejszy od $Q$, jeżeli dla pewnego $r$ ($1 \le r \le s$ oraz $r \le t$) mamy $p_1=q_1,\ldots,p_{r-1}=q_{r-1}$ i $p_r<q_r$ ($p_r$ jest liczbowo mniejsze od $q_r$).

Ścieżka odwiedzająca ten sam wierzchołek dwa lub więcej razy jest zabroniona.

Przykład

Wejście 1

5 20 10 1 5
1 2 1
1 3 2
1 4 1
1 5 3
2 1 1
2 3 1
2 4 2
2 5 2
3 1 1
3 2 2
3 4 1
3 5 1
4 1 1
4 2 1
4 3 1
4 5 2
5 1 1
5 2 1
5 3 1
5 4 1
4 6 1 1 4
2 4 2
1 3 2
1 2 1
1 4 3
2 3 1
3 4 1
3 3 5 1 3
1 2 1
2 3 1
1 3 1
0 0 0 0 0

Wyjście 1

1-2-4-3-5
1-2-3-4
None

Uwagi

W pierwszym zestawie istnieje 16 ścieżek z wierzchołka $1$ do $5$. Są uporządkowane następująco (liczba w nawiasach to długość ścieżki).

1. $(3)$ 1-2-3-5

2. $(3)$ 1-2-5

3. $(3)$ 1-3-5

4. $(3)$ 1-4-3-5

5. $(3)$ 1-4-5

6. $(3)$ 1-5

7. $(4)$ 1-4-2-3-5

8. $(4)$ 1-4-2-5

9. $(5)$ 1-2-3-4-5

10. $(5)$ 1-2-4-3-5

11. $(5)$ 1-2-4-5

12. $(5)$ 1-3-4-5

13. $(6)$ 1-3-2-5

14. $(6)$ 1-3-4-2-5

15. $(6)$ 1-4-3-2-5

16. $(8)$ 1-3-2-4-5