中文翻译

题目描述：

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

迷宫所有者计划明天举办一场比赛。多名参赛者将从$1$号房间出发，跑到$n$号房间，并记录沿途经过的通道颜色。颜色序列最短的参赛者获胜。如果有多名参赛者的序列长度相同，则颜色序列字典序最小的路径（称为理想路径）的参赛者获胜。

Andrew正在为比赛做准备。他乘坐直升机拍摄了迷宫的地图。你的任务是帮助他找到从$1$号房间到$n$号房间的理想路径，以便他赢得比赛。

注意：

序列$(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$。

输入：

第一行包含两个整数$n$和$m$，分别表示房间数和通道数（$2 \leq n \leq 100\,000$，$1 \leq m \leq 200\,000$）。接下来的$m$行描述通道，每行包含三个整数：$a_i$、$b_i$和$c_i$，表示通道连接的两个房间编号及其颜色（$1 \leq a_i, b_i \leq n$，$1 \leq c_i \leq 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

输出样例 1：

2
1 3