Isaac 厌倦了每天沿着同一条最短路线去办公室。虽然这样节省时间，但他不得不反复看到相同的景色。他再也无法忍受如此无聊的通勤了。

一天，他决定改善这种状况。他要每天至少稍微改变路线。新方案如下：第一天使用最短路线；第二天使用第二短路线，也就是除第一天所用路线外最短的路线。一般而言，第 $k$ 天选择第 $k$ 短路线。当然，应避免在一条路线上两次到访同一地点。

请编写程序帮助 Isaac 找到第 $k$ 天的路线。这个问题很容易用图论术语建模。你的程序应在给定有向图中找到第 $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$ 的边，否则不能从 $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。注意 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