题目描述
给定一个有n 个节点、m 条边的无向图，每条边都涂有1种颜色。求节点1到n 的一条路径，使得经过的边数最少，在此前提下，经过边的颜色序列最小。可能有自环与重边。
输入保证至少存在一条连接节点1和n 的路径。
输入
输入共m +1行。第1行包含两个整数：n 和m 。之后的m行，每行都包含3个整数ai 、bi 、ci ，表示在ai 、bi 之间有一条颜色为ci 的路径。
输出
输出共两行，第1行包含正整数k ，表示节点1到n 至少需要经过k 条边。第2行包含k 个由空格隔开的正整数，表示节点1到n依次经过的边的颜色。
4 6
1 2 1
1 3 2
3 4 3
2 3 1
2 4 4
3 1 1
提示
输出样例解释：
节点1到4至少经过两条边：1->3，颜色为1（最后输入的那条边）；3->4，颜色为3。
数据范围：2≤n≤105,1≤m≤105,1≤ci≤109，对于任意i∈[1，m]，都有1≤ai，bi≤n。对于两个长度为k的序列a和b，若存在i∈[1，k]使ai<bi，且对于任意j∈[1，i)都有aj=bj，则a<b。