题目描述

众所周知，生成树问题是数据结构课程（或离散数学）中的一道经典例题。

RT，现在有一个简单的生成树问题。

给你一个$n$个点，$m$条边的图，每条边权都有固定的权值$w$。然后你现在的任务是求出该图的最小生成树。

当然,既然本题作为比赛中的一道，所以它的难度肯定不止简单的权值和问题。

请你输出最小生成树的权值和以及所有可能的最小生成树的边的并集。

特殊的，如果该图不能生成一颗最小生成树，请输出$-1$。

输入格式

本题为多组输入，第一行输入一个$T$，表示有$T$组数据。

接下来$T$组数据，每组数据第一行，输入两个数$n,m$，表示有$n$个点，$m$条边。

接下来$m行$，每行输入$3$个数$u,v,w$，表示第$i$条边的两个端点以及对应的边权。

数据保证，$T\in[10,50],n\in[1,2 \times 10^5],m\in[1,2 \times 10^5],w\in[1,10^9], \sum n \leq 2 \times 10^5$。

输出格式

输出$T$行，对于每一组数据，第一行输出对应的权值和，接下来一行输出所有的边的编号（按输入顺序从小到大输出），每组数据输出完之后需换行。

样例

1
6 7
1 6 4
1 2 3
2 3 3
2 5 3
1 5 1
3 5 3
4 2 3

14
1 2 3 4 5 6 7

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

-1