题目描述

校园网是为学校师生提供资源共享、信息交流和协同工作的计算机网络。校园网是一个宽带、具有交互功能和专业性很强的局域网络。如果一所学校包括多个学院及部门，也可以形成多个局域网络，并通过有线或无线方式连接起来。原来的网络系统只局限于以学院、图书馆为单位的局域网，不能形成集中管理以及各种资源的共享，个别学院还远离大学本部，这些情况严重地阻碍了整个学校的网络化需求。

无向图 $G=(V,E)$ 来表示通信网络，$V$ 表示顶点集，$E$ 表示边集。把各个单位抽象为图中的顶点，顶点与顶点之间的边表示单位之间的通信网络，边的权值表示布线的费用。如果两个节点之间没有连线，代表这两个单位之间不能布线，费用为无穷大。现在需要设计网络电缆布线，将各个单位的局域网络连通起来，如何设计能够使费用最少呢？如果无法连通则输出 $-1$。

输入格式

第一行是一个整型数 $T$ 表示共有 $T$ 组测试数据。

每组测试数据的第一行是两个整数 $n,m$ 表示该测试数据有 $n$ 个顶点 $m$ 条边。

随后的 $m$ 行，每行有 $3$ 个正整数 $u,v,w$，分别表示边的两个顶点编号 $u,v$ 及两顶点之间的费用。

数据范围：$0<T≤10, 1≤n,m,u,v,w≤10^4, 1≤u,v≤n$。

输出格式

对于每一组输入，输出一行，表示最小费用值。

样例

2
7 12
1 2 23
1 6 28
1 7 36
2 3 20
2 7 1
3 4 15
3 7 4
4 5 3
4 7 9
5 6 17
5 7 16
6 7 25
4 6
1 2 10
1 4 5
1 3 8
2 3 8
2 4 11
3 4 8

57
21