最优路径

【题目描述】

给定一个$n$个点$m$条边的无向图，每条边的长度都为$1$，且有一个颜色。 找一条从节点$1$到节点$n$的路径，使得这条路径在包含的边数最少的前提下，路径上的边的颜色顺次连接形成的序列的字典序最小。

【输入】

输入包含多组数据。 第一行一个整数表示数据组数。 对于每组数据： 第一行两个整数$n$和$m$。 接下来$m$行，每行三个整数$a_i，b_i$和$c_i$，表示存在一条双向边($a_i,b_i$)，颜色为$c_i$。

【输出】

第一行一个整数，表示最短路径$dis$。 第二行$dis$个整数，表示路径上的边的颜色顺次连接形成的序列。

【输入样例】

1
4 6
1 2 1
1 3 2
3 4 3
2 3 1
2 4 4
3 1 1

【输出样例】

2
1 3

【提示】

【数据规模】 对于100%的数据，$2≤n≤100000，1≤m≤200000，1≤a_i,b_i≤n，1≤c_i≤10^9$。