1481: 理想路径
Memory Limit：128 MB
Time Limit：1.000 S
Judge Style：Text Compare
Creator：
Submit：6
Solved：6
Description
对于n个房间m条路径的迷宫（2<=n<=10000, 1<=m<=20000），每条路径上都涂有颜色，颜色取值范围为c（1<=c<=109）。求从节点1到节点n的一条路径，使得经过的边尽量少，在这样的前提下，如果有多条路径边数均为最小，则颜色的字典序最小的路径获胜。一条路径可能连接两个相同的房间，一对房间之间可能有多条路径。输入保证可以从节点1到达节点n。
Input
第一行，输入n和m（2<=n<=10000, 1<=m<=20000）
以下的m行，每行3个数据ai，bi，ci（2<=ai，bi<=10000，1<=c<=109）
Output
第一行，输出起点到终点的最短路长度
第二行，输出从起点到终点最短路的颜色序列，用空格分开。
Sample Input Copy
4 6
1 2 1
1 3 2
3 4 3
2 3 1
2 4 4
3 1 1Sample Output Copy
2
1 3
HINT
【样例输入2】
4 3
1
2 1
1
3 1
1
4 7
【样例输出2】
1
7