P3708.第3题-游乐园
题目内容
游乐园开放了一个新的迷宫景点。迷宫由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≤109)。每条通道都可以双向通过。两个房间可以用多条通道连接，也可以有从一个房间到自身的通道。保证可以从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
