题目描述

在新迷失之地游乐园开放了一个新的迷宫景点。迷宫由 $n$ 个房间通过 $m$ 个通道连接而成，每个通道都被染上一种颜色 $c_{i}$。游客们被从直升机投放到1号房间，他们的目标是到达位于 $n$ 号房间的迷宫出口。

迷宫的所有者计划明天举办一场比赛。几名参赛者将被放到 $1$ 号房间，他们将跑到 $n$ 号房间，记录他们穿过的通道的颜色。

具有最短颜色序列的参赛者将成为比赛的获胜者。如果有多个参赛者的序列长度相同，那么颜色序列在最短路径中是字典序最小的参赛者将成为获胜者。

现在，Andrew正在为比赛做准备。他乘直升机在新迷失之地上空拍摄了迷宫的照片。你的任务是帮助他找到从 $1$ 号房间到 $n$ 号房间的理想路径，从而使他赢得比赛。

注意：

如果存在 $i$，使 $a_{i} < b_{i}$，并且对于所有的 $j < i$，都有 $a_{j} = b_{j}$，则序列（$a_{1}, a_{2},\dotsb, a_{k}$）比序列（$b_{1}, b_{2},\dotsb, b_{k}$）字典上小。

简易题面

给定一个无向图（可能有重边），每条边都有一种颜色，边权为 $1$。你需要找到从 $1$ 到 $n$ 的最短路径，并且经过的边的颜色组成的序列的字典序最小。

输入格式

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

接下来 $m$ 行描述通道，每行包含三个整数： $a_{i},b_{i},c_{i}$，表示连接起点和终点的房间号以及通道的颜色。每个通道都可以沿着任意方向被通过。两个房间可以通过多条通道相连，也有可能存在从一个房间到自身的通道。

保证可以从 $1$ 号房间到 $n$ 号房间有通路。

输出格式

输出的第一行包含一个整数 $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

数据范围

对于 $100\%$ 的数据，$2 \leq n \leq 1 \times 10^5$，$1 \leq m \leq 2 \times 10^5$，$1 \leq a_{i}, b_{i} \leq n$，$1 \leq c_{i} \leq 10^9$。

题目来源

Pku3967