[SCOI2007]kshort

有 $n$ 个城市和 $m$ 条单向道路，城市编号为 $1\sim n$。每条道路连接两个不同的城市，且任意两条道路的起点或终点至少有一个不同，因此 $m\le n(n-1)$。

给定两个城市 $a$ 和 $b$，将所有从 $a$ 到 $b$ 的简单路径进行排序。简单路径是指路径上的所有城市（包括起点和终点）至多经过一次。排序时，首先按照路径长度从小到大排列；若路径长度相同，则按照路径经过的城市序列的字典序从小到大排列。

请你求出从城市 $a$ 到城市 $b$ 的第 $k$ 短路。

输入格式

第一行包含 $5$ 个正整数 $n,m,k,a,b$。

接下来 $m$ 行，每行包含 $3$ 个整数 $u,v,l$，表示存在一条从城市 $u$ 到城市 $v$、长度为 $l$ 的单向道路。

输出格式

如果从城市 $a$ 到城市 $b$ 的简单路径不足 $k$ 条，输出 No。

否则，输出第 $k$ 短路经过的城市序列：从城市 $a$ 开始，依次输出路径经过的每个城市，直到城市 $b$，相邻城市之间用减号 - 分隔。

样例输入

样例 $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

样例 $2$

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 3 5 1 3
1 2 1
2 3 1
1 3 1

样例输出

样例 $1$

1-2-4-3-5

样例 $2$

1-2-3-4

样例 $3$

No

样例解释

在样例 $1$ 中，共有 $5$ 个城市，所有可能的单向道路均存在。从城市 $1$ 到城市 $5$ 共有 $16$ 条简单路径，按照题目规定排序后，第 $10$ 条路径为 1-2-4-3-5。

数据范围

• $2\le n\le 50$；
• $1\le m\le n(n-1)$；
• $1\le k\le 200$；
• $1\le a,b,u,v\le n$；
• $u\ne v$；
• $1\le l\le 10^4$。

来源与许可

本题为 SCOI 2007 试题「kshort」，题面与测试数据整理自 BZOJ。

样例 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

输出

1-2-4-3-5

样例 2

输入

4 6 1 1 4
2 4 2
1 3 2
1 2 1
1 4 3
2 3 1
3 4 1

输出

1-2-3-4

样例 3

输入

3 3 5 1 3
1 2 1
2 3 1
1 3 1

输出

No