Isaac は毎日同じ最短ルートで職場へ行くことに飽きています。時間は節約できますが、同じ景色を何度も見なければなりません。もうこんな退屈な通勤には耐えられません。

ある日、彼は状況を改善することにしました。毎日少なくとも少しはルートを変えます。新しい方法は次の通りです。1 日目は最短ルートを使います。2 日目は 2 番目に短いルート、つまり 1 日目に使ったもの以外で最短のルートを使います。一般に $k$ 日目には $k$ 番目に短いルートを選びます。もちろん、1 つのルートで同じ場所を 2 回訪れることは避けるべきです。

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

データセット中の各入力項目は非負整数です。同じ行にある 2 個以上の項目は空白で区切られます。

$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)$ の両方の場合が含まれます。

最後のデータセットの後に、空白で区切られた 5 個の 0 を含む行があります。

出力

各データセットについて、以下の指定に従い 1 行を出力してください。空白などの余計な文字を含めてはいけません。

$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$ より先です。

同じ頂点を 2 回以上訪れるパスは許されません。

入出力例

入力 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