Isaac은 매일 같은 최단 경로로 사무실에 가는 것이 지겹습니다. 시간은 절약되지만 같은 풍경을 반복해서 봐야 합니다. 더 이상 이렇게 지루한 통근을 견딜 수 없습니다.

어느 날 상황을 개선하기로 했습니다. 매일 경로를 적어도 조금씩 바꿀 것입니다. 새 계획은 다음과 같습니다. 첫날에는 최단 경로를 이용합니다. 둘째 날에는 두 번째로 짧은 경로, 즉 첫날 사용한 경로를 제외하고 가장 짧은 경로를 이용합니다. 일반적으로 $k$번째 날에는 $k$번째로 짧은 경로를 선택합니다. 물론 하나의 경로에서 같은 장소를 두 번 방문하는 것은 피해야 합니다.

$k$번째 날의 경로를 찾는 프로그램을 작성하여 Isaac을 도와주세요. 이 문제는 그래프 이론 용어로 쉽게 모델링됩니다. 프로그램은 주어진 방향 그래프에서 $k$번째로 짧은 경로를 찾아야 합니다.

입력

입력은 여러 데이터셋으로 이루어지며, 각 형식은 다음과 같습니다.

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

데이터셋의 모든 입력 항목은 음이 아닌 정수입니다. 한 줄에 두 개 이상의 항목이 있으면 공백으로 구분됩니다.

$n$은 그래프의 정점 수이며 $2 \le n \le 50$이라고 가정할 수 있습니다. $m$은 (방향) 간선 수입니다. $a$는 시작 정점, $b$는 목표 정점이며, 둘 다 $1$부터 $n$까지입니다. $a$에서 $b$까지 $k$번째로 짧은 경로를 찾아야 합니다. $1 \le k \le 200$ 및 $a \ne b$라고 가정할 수 있습니다.

$i$번째 간선은 정점 $x_i$에서 $y_i$로 향하며 길이는 $d_i$입니다 ($1 \le i \le m$). $x_i,y_i$는 $1$부터 $n$까지, $d_i$는 $1$부터 $10000$까지입니다. $x_i$에서 $y_i$로 직접 갈 수 있지만, $y_i$에서 $x_i$로의 간선이 명시적으로 주어지지 않으면 역방향으로 갈 수 없습니다. 같은 정점 쌍을 연결하는 간선은 존재한다면 유일합니다. 즉 $i \ne j$일 때 $x_i=x_j$와 $y_i=y_j$가 동시에 성립하지 않습니다. 자기 자신으로 연결되는 간선은 없으므로 $x_i$는 $y_i$와 같지 않습니다. 따라서 $0 \le m \le n(n-1)$입니다.

주어진 그래프는 도로망으로서 매우 비현실적일 수 있습니다. 평가 데이터에는 $m=0$인 경우와 $m=n(n-1)$인 경우 모두 포함됩니다.

마지막 데이터셋 뒤에는 공백으로 구분된 다섯 개의 0이 있는 줄이 주어집니다.

출력

각 데이터셋에 대해 아래 규칙에 따라 한 줄을 출력하세요. 출력 줄에는 공백 등의 여분 문자가 없어야 합니다.

$a$에서 $b$까지 서로 다른 경로 수가 $k$보다 작으면 None을 출력하세요. 첫 글자는 대문자이며 나머지는 소문자입니다.

$a$에서 $b$까지 서로 다른 경로 수가 $k$ 이상이면, $k$번째로 짧은 경로에서 방문하는 정점 번호를 방문 순서대로 하이픈 (마이너스 기호)으로 구분하여 출력하세요. $a$가 첫 번째, $b$가 마지막이어야 합니다.

이 문제에서 “더 짧다” (따라서 “가장 짧다”도)는 특별한 의미입니다. 다음 중 하나가 성립할 때, 그리고 그때에만 경로 $P$가 $Q$보다 짧다고 정의합니다.

1. $P$의 길이가 $Q$의 길이보다 작습니다. 경로의 길이는 경로에 있는 간선 길이의 합입니다.

2. $P$와 $Q$의 길이가 같고, $P$의 정점 번호열이 사전순으로 $Q$보다 앞섭니다. 정확히는 $P$의 번호열을 $p_1,p_2,\ldots,p_s$, $Q$의 번호열을 $q_1,q_2,\ldots,q_t$라고 합시다. $p_1=q_1=a$ 및 $p_s=q_t=b$입니다. 어떤 $r$ ($1 \le r \le s$ 및 $r \le t$)에 대해 $p_1=q_1,\ldots,p_{r-1}=q_{r-1}$이고 $p_r<q_r$ ($p_r$의 수치가 $q_r$보다 작음)이면 $P$가 $Q$보다 사전순으로 앞섭니다.

같은 정점을 두 번 이상 방문하는 경로는 허용되지 않습니다.

예제

입력 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

출력 1

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

참고

첫 번째 데이터셋에는 정점 $1$에서 $5$까지 16개의 경로가 있습니다. 다음 순서로 정렬됩니다 (괄호 안 수는 경로 길이입니다).

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