Isaac está cansado de ir diariamente a su oficina por la misma ruta más corta. Aunque ahorra tiempo, debe ver el mismo paisaje una y otra vez. Ya no soporta un trayecto tan aburrido.

Un día decidió mejorar la situación. Cambiaría su ruta cada día, aunque fuera ligeramente. Su nuevo plan es el siguiente: el primer día usa la ruta más corta. El segundo día usa la segunda más corta, es decir, la más corta excepto la usada el primer día. En general, el día $k$ elige la $k$-ésima ruta más corta. Por supuesto, debe evitar visitar dos veces el mismo lugar en una ruta.

Te invitamos a ayudar a Isaac escribiendo un programa que encuentre su ruta del día $k$. El problema se modela fácilmente con términos de teoría de grafos. Tu programa debe encontrar el $k$-ésimo camino más corto del grafo dirigido dado.

Entrada

La entrada consta de varios conjuntos de datos, cada uno con el siguiente formato.

$$\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}$$

Cada elemento de entrada de un conjunto es un entero no negativo. Si hay dos o más elementos en una línea, se separan por espacios.

$n$ es el número de nodos del grafo. Puedes suponer $2 \le n \le 50$. $m$ es el número de aristas (dirigidas). $a$ es el nodo inicial y $b$ el destino. Ambos están entre $1$ y $n$, inclusive. Debes encontrar el $k$-ésimo camino más corto de $a$ a $b$. Puedes suponer $1 \le k \le 200$ y $a \ne b$.

La $i$-ésima arista va del nodo $x_i$ al $y_i$ y tiene longitud $d_i$ ($1 \le i \le m$). Tanto $x_i$ como $y_i$ están entre $1$ y $n$, inclusive, y $d_i$ entre $1$ y $10000$, inclusive. Puedes ir directamente de $x_i$ a $y_i$, pero no de $y_i$ a $x_i$ salvo que se dé explícitamente una arista de $y_i$ a $x_i$. Si existe una arista para una misma pareja de nodos, es única: si $i \ne j$, nunca se cumplen simultáneamente $x_i=x_j$ e $y_i=y_j$. Las aristas no conectan un nodo consigo mismo, es decir, $x_i$ nunca es igual a $y_i$. Por tanto, $0 \le m \le n(n-1)$.

El grafo dado puede ser muy poco realista como red de carreteras. Los datos de evaluación incluyen tanto $m=0$ como $m=n(n-1)$.

Después del último conjunto hay una línea con cinco ceros separados por espacios.

Salida

Para cada conjunto de entrada, imprime una línea según se especifica a continuación. Una línea de salida no debe contener caracteres adicionales, como espacios.

Si el número de caminos distintos de $a$ a $b$ es menor que $k$, imprime la cadena None. Su primera letra está en mayúscula y las demás en minúscula.

Si hay al menos $k$ caminos distintos de $a$ a $b$, imprime los números de los nodos visitados en el $k$-ésimo camino más corto, en orden de visita, separados por un guion (signo menos). $a$ debe ser el primero y $b$ el último de la línea.

En este problema, “más corto” (y, por tanto, “el más corto”) tiene un significado especial. Un camino $P$ es más corto que $Q$ si y solo si se cumple una de las siguientes condiciones.

1. La longitud de $P$ es menor que la de $Q$. La longitud de un camino se define como la suma de las longitudes de sus aristas.

2. Las longitudes de $P$ y $Q$ son iguales, y la secuencia de números de nodos de $P$ precede a la de $Q$ en orden lexicográfico. Más precisamente, denotemos la secuencia de $P$ por $p_1,p_2,\ldots,p_s$ y la de $Q$ por $q_1,q_2,\ldots,q_t$. Se tiene $p_1=q_1=a$ y $p_s=q_t=b$. La secuencia $P$ precede a $Q$ si, para algún $r$ ($1 \le r \le s$ y $r \le t$), $p_1=q_1,\ldots,p_{r-1}=q_{r-1}$ y $p_r<q_r$ ($p_r$ es numéricamente menor que $q_r$).

No se permite un camino que visite el mismo nodo dos o más veces.

Ejemplos

Entrada 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

Salida 1

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

Nota

En el primer conjunto hay 16 caminos del nodo $1$ al $5$. Se ordenan de la siguiente manera (el número entre paréntesis es la longitud del camino).

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