思路

这个问题可以分解为两个主要步骤：

1. 找到从房间 $1$ 到房间 $N$ 的最短路径长度。
2. 在所有最短路径中，找到颜色序列字典序最小的那一条。

第一步：计算最短路径长度

图中每条通道的长度都为 $1$，因此这是一个无权图的最短路径问题。解决此类问题的经典算法是广度优先搜索（BFS）。

题目内容

游乐园开放了一个新的迷宫景点。迷宫由$N$个房间组成，通过$M$条通道连接。每条通道都涂有某种颜色$Ci$。迷宫的游客从直升机降落到$1$号房间，他们的目标是到达位于$N$号房间的迷宫出口。

迷宫的主人计划明天举办一场比赛。几名参赛者将被投放到$1$号房间。他们将跑向$N$号房 间，并在通过通道时记录下通道的颜色。拥有最短颜色序列的参赛者是比赛的获胜者

如果有几个参赛者的序列长度相同，那么拥有理想路径的人获胜。如果一条路径的颜色序列在所有最短路径中字典序最小，那么这条路径就是理想路径。

安德鲁正在为比赛做准备。他乘坐直升机在新失落乐园上空观光，并拍摄了迷官的照片。您的任务是帮助他找到从$1$号房间到N号房间的理想路径，使他能够赢得比美

注释

当存在$i$使得$Ai<Bi$，且对于所有$j<i$都有$Aj=Bj$时，序列$(A1,A2,...,Ak)$在字典序上小于序列$(B1, B2,.... Bk)$。

输入描述

输入第一行包含整数N和M分别表示房间数量和通道数量$(2≤N≤100,000,1≤M ≤200,000)$

接下来的$m$行描述通道，每条通道用三个整数描述:$Ai、Bi$和$Ci$—它连接的房间号码和它的颜色$(1≤Ai,Bi≤n，1≤Ci≤10^9)$。每条通道都可以双向通过。两个房间可以用多条通道连接，也可以有从一个房间到自身的通道。保证可以从$1$号房间到达$N$号房间。

输出描述

输出的第一行必须包含$k$从$1$号房间到$N$号房间的最短路径长度。第二行必须包含$k$个数字——理想路径中按通过顺序排列的通道颜色。

样例1

输入

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

输出

2
1 3