Pku3967 Ideal Path

新迷宫景点在 New Lostland 游乐园开放了。迷宫由 $n$ 个房间和 $m$ 条通道组成，每条通道都有一种颜色。游客会从直升机降落到编号为 $1$ 的房间，目标是到达位于编号为 $n$ 的房间中的出口。

游乐园管理者计划在明天举行一场比赛。参赛者从房间 $1$ 出发，沿通道前进，并依次记录经过通道的颜色。经过的颜色序列长度最短的参赛者获胜；如果有多名参赛者经过的颜色序列长度相同，则颜色序列按字典序最小的参赛者获胜。这样的路径称为理想路径。

请你求出一条从房间 $1$ 到房间 $n$ 的理想路径。

如果两个长度均为 $k$ 的序列 $(a_1,a_2,\ldots,a_k)$ 和 $(b_1,b_2,\ldots,b_k)$ 满足：存在某个位置 $i$，使得 $a_i<b_i$，且对于所有 $j<i$ 都有 $a_j=b_j$，则称序列 $(a_1,a_2,\ldots,a_k)$ 的字典序小于序列 $(b_1,b_2,\ldots,b_k)$。

时间限制：$10000\ \text{ms}$；内存限制：$131072\ \text{KB}$。

输入格式

第一行包含两个整数 $n$ 和 $m$，分别表示房间数和通道数。

接下来 $m$ 行，每行包含三个整数 $a_i$、$b_i$ 和 $c_i$，表示一条连接房间 $a_i$ 和房间 $b_i$ 的通道，其颜色为 $c_i$。每条通道均可双向通行。

输出格式

第一行输出整数 $k$，表示从房间 $1$ 到房间 $n$ 的最短路径长度。

第二行输出 $k$ 个整数，表示理想路径上依次经过的通道颜色。

样例输入

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

样例输出

2
1 3

数据范围

• $2\le n\le 10^5$，且 $1\le m\le 2\times 10^5$；
• $1\le a_i,b_i\le n$；
• $1\le c_i\le 10^9$；
• 图中允许存在重边，也允许存在连接房间自身的自环；
• 保证从房间 $1$ 可以到达房间 $n$。

来源与许可

本题题面与测试数据整理自 BZOJ 2644。

样例 1

输入

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

输出

2
1 3