Enjoyable Communication

아이작은 매일 같은 최단 경로로 회사에 출근하는 일에 지쳤다. 시간은 아낄 수 있지만 늘 똑같은 풍경만 봐야 해서, 이 지루한 출근을 더는 견딜 수 없게 되었다.

어느 날 그는 매일 조금씩 다른 경로로 다니기로 했다. 그의 계획은 이렇다. 첫째 날에는 최단 경로를 이용하고, 둘째 날에는 두 번째로 짧은 경로(첫째 날에 이용한 경로를 제외한 최단 경로)를 이용한다. 일반적으로 $k$번째 날에는 $k$번째로 짧은 경로를 이용한다. 물론 한 경로에서 같은 곳을 두 번 방문해서는 안 된다.

아이작을 도와, $k$번째 날에 그가 이용할 경로를 찾는 프로그램을 작성하라. 이 문제는 그래프 이론으로 간단히 모델링할 수 있다. 즉, 주어진 방향 그래프에서 $k$번째로 짧은 경로를 찾으면 된다.

입력은 여러 개의 데이터셋으로 이루어져 있으며, 각 데이터셋의 형식은 다음과 같다.

n m k a b
x1 y1 d1
x2 y2 d2
...
xm ym dm

데이터셋의 모든 값은 음이 아닌 정수이며, 한 줄에 있는 값들은 공백 하나로 구분된다.

$n$은 그래프의 정점 개수로 $2 \le n \le 50$이다. $m$은 방향 간선의 개수이다. $a$는 시작 정점, $b$는 도착 정점이며 둘 다 $1$ 이상 $n$ 이하이고 $a \ne b$이다. $a$에서 $b$로 가는 $k$번째 최단 경로를 찾아야 하며, $1 \le k \le 200$이다.

$i$번째 간선($1 \le i \le m$)은 정점 $x_i$에서 정점 $y_i$로 향하고 길이는 $d_i$이다. 여기서 $x_i$와 $y_i$는 $1$ 이상 $n$ 이하이고, $1 \le d_i \le 10000$이다. 이 간선으로 $x_i$에서 $y_i$로 직접 이동할 수 있지만, 반대 방향 간선이 따로 주어지지 않는 한 $y_i$에서 $x_i$로는 이동할 수 없다. 임의의 정점 순서쌍에 대해 간선은 많아야 하나이며, 자기 자신으로 향하는 간선은 없다($x_i \ne y_i$). 따라서 $0 \le m \le n(n-1)$이 성립한다.

그래프는 현실적인 도로망과 전혀 다를 수 있다. $m = 0$인 경우와 $m = n(n-1)$인 경우가 모두 데이터에 포함된다.

마지막 데이터셋 다음에는 공백으로 구분된 다섯 개의 $0$이 있는 줄이 온다.

각 데이터셋에 대해 아래 규칙에 따라 정확히 한 줄을 출력한다. 줄 끝 공백 같은 불필요한 문자를 포함해서는 안 된다.

$a$에서 $b$로 가는 서로 다른 경로의 개수가 $k$보다 적으면 문자열 None을 출력한다(첫 글자 N은 대문자, 나머지는 소문자).

그렇지 않으면 $k$번째 최단 경로에서 방문하는 정점 번호를 방문 순서대로 하이픈(-)으로 구분하여 출력한다. 첫 번째 번호는 반드시 $a$, 마지막 번호는 반드시 $b$여야 한다.

이 문제에서 더 짧다(따라서 가장 짧다)는 특별한 의미를 가진다. 경로 $P$가 경로 $Q$보다 짧다는 것은 다음 중 하나가 성립하는 경우이며, 그 경우에만 성립한다.

• $P$의 길이가 $Q$의 길이보다 작다. 경로의 길이는 그 경로에 속한 간선 길이의 합이다.
• $P$와 $Q$의 길이가 같고, $P$의 정점 번호 수열이 사전식(lexicographic) 순서로 $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$가 $Q$보다 앞선다.

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