理想路径 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<b$。
原文：A sequence (a1, a2, . . . , ak) is lexicographically smaller than a sequence (b1, b2, . . . , bk) if there
exists i such that ai < bi
, and aj = bj for all j < i.
感谢@Sparky_14145 提供的翻译
题目描述
[problemUrl]: https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=448&page=show_problem&problem=4474
[PDF](https://uva.onlinejudge.org/external/15/p1599.pdf)