Description

给定n(n<=500)个顶点,以及E(E<=20000)条边，计算最小生成树的权值.

Input

第一行输入T表示有T组数据。每组数据第一行输入n、E，分别表示顶点数和边数. 接下来
输入E行每行三个正整数u(1<=u<=n)、v(1<=v<=n)、w，表示顶点u到顶点v之间无向边
长度w（可能有重边）。

Output

输出T行正整数，第i行表示第i组数据的最小生成树权值, 若不能构建最小生成树输出-1。

Sample Input

3
2 2
1 2 1
1 2 2
3 1
2 3 1
3 3
1 2 2
1 2 3
2 3 1

Sample Output

1
-1
3