题目描述

给定一个$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$。

完整数据范围与边界约定

1≤T≤10；每组2≤n≤100000，0≤m≤200000，端点1..n，1≤颜色≤10^9；允许重边和自环。所有数据组的n+m之和不超过10^6。若1不能到达n，第一行输出-1、第二行为空行；否则按原要求输出最短边数及恰好该长度的颜色序列，整数颜色按数值比较。

本地修订与来源

本题为经授权补全的本地训练修订版，原始公开题面保留在采集档案；修订了：1≤T≤10；每组2≤n≤100000，0≤m≤200000，端点1..n，1≤颜色≤10^9；允许重边和自环。所有数据组的n+m之和不超过10^6。若1不能到达n，第一行输出-1、第二行为空行；否则按原要求输出最短边数及恰好该长度的颜色序列，整数颜色按数值比较。。此处题意、范围和输出约定以本修订版为准，不冒称原站或官方原版。原题链接：https://ybt.ssoier.cn/problem_show.php?pid=1688。

评测数据说明

本题使用按题意独立构造、以独立程序核对的训练数据及公开样例，共5个测试点，非原站或官方原始数据。总分100分。