UVA1599 理想路径 Ideal Path
题目描述
## 本题有多组数据
# 理想路径（Ideal Path, NEERC 2010, UVa1599）
给定一个$n$个点$m$条边的无向图，每条边上都涂有1种颜色。求点$1$到点$n$的一条路径，**使得经过的边数最少**，在此前提下，经过边的颜色序列最小。可能有自环与重边。输入保证至少存在一条连接$1$和$n$的道路。
输入格式
输入共$m+1$行：
第一行$2$个空格整数：$n$和$m$。
以后$m$行，每行空格隔开的$3$个整数$a_i,b_i,c_i$，表示在$a_i,b_i$之间有一条颜色为$c_i$的道路。
输出格式
输出共两行：
第一行$1$个正整数$k$，表示$1$到$n$至少需要经过$k$条边。
第二行包含$k$个空格隔开的正整数，表示从$1$到$n$依次经过的边的**颜色**。
## 输入输出样例：
### 输入样例：
```
4 6
1 2 1
1 3 2
3 4 3
2 3 1
2 4 4
3 1 1
```
### 输出样例：
```
2
1 3
```
### 输入输出样例解释：
路径依次如下：
$1\rightarrow3$，颜色为$1$（最后输入的那条）；
$3\rightarrow4$，颜色为$3$。
说明/提示
$2\leq n \leq 10^5, 1 \leq m \leq 2 \times 10^5,1\leq c_i \leq 10^9$。
对于任意$i \in [1,m]$有$1 \leq a_i,b_i \leq n$。
注：对于两个长度为$k$的序列$a,b$，当存在$i \in [1,k]$使$a_i < b_i$，且对于任意$j \in [1,i)$都有$a_j = b_j$时，$a