【题目描述】

给定一张 $n$ 个节点带正边权有向简单图，求第 $k$ 短 $1$ 到 $n$ 的简单路径。

形式化地，一条简单路径定义为序列 $(p_1,p_2,p_3....p_l$ 满足：

• $p_1 = 1, p_l = n$。
• $\forall 1 \le i < l$，存在 $p_i$ 连向 $p_{i+1}$ 的有向边。 • $\forall 1 \le i < j \le l, pi \neq pj$。

定义其权值为经过的有向边的权值和。

称简单路径 $p$ 比简单路径 $q$ 短，当且仅当以下至少一条成立：

• $p$ 的权值小于 $q$ 的权值。

• $p$ 的权值等于 $q$ 的权值，且序列 $(p_1,... , p_l)$ 的字典序小于序列 $(q_1, ...., q_r)$。

【输入格式】

第一行三个整数 $n, m, k$。 接下来 $m $ 行，每行三个整数 $u, v, w$，表示从 $u \rightarrow v$ 且权值为 $w$ 的有向边。

【输出格式】

若无解输出一行一个整数 $−1$。 否则，第一行一个整数 $l$ ，表示答案路径 $p$ 的点数。 第二行 $l$ 个整数，依次为 $p_1, p_2, .... , pl$ 。

【样例1输入】

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

【样例1输出】

4
1 2 3 4

【样例2输入】

5 20 10
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输出】

5
1 2 4 3 5

【样例3输入】

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

【样例3输出】

-1