Description

给出一个无向网，求该无向网的最小生成树。各条边的权重不超过100000。

Input

输入的第一行是一个int型整数T，表示一个有T组数据。
每组数据第一行包含两个数n，m。n表示该网的顶点个数,3 ≤ N ≤ 100,m 表示无向边的个数。
接下来有m行，每行三个数，ai,bi,ci,表示点ai到点bi有一条权重为ci的边。

Output

输出该最小生成树的权重。保证最小生成树存在。

Sample Input

1
4 5
1 2 4
1 3 9
2 3 8
4 3 16
2 4 17

Sample Output

28