题目描述

今天是断罪中学的“科学才能展示日”，李子明同学展示的是他精心设计的电路结构。电路中共有\(N\)个节点，一些节点之间会有一段导线直接相连，共计\(M\)段导线。根据物理学知识：
1. 电流必然形成若干条回路；
2. 对于每个节点，流入的电流之和等于流出的电流之和。
由于导线的材料、长度、粗细会影响电阻大小，因此每段导线上的电流大小可能会不相同。李子明同学想要测量每一段导线上的电流大小。每一段导线上都可以安装一个电流计，在第\(i\)段导线上安装的成本为\(c_i\)（\(1 \le i \le M\)，注意成本可能为负数）。实际操作时，我们可以直接测量一部分导线的电流大小，然后利用以上两条电流回路的性质，间接算出另外几段导线各自的电流。例如3个节点、3段导线的回路A-B-C-A，我们只需要直接测量A-B、B-C或C-A中的任意一段，就可以推算出3段导线各自的电流。再例如4个节点、6段导线的回路，节点A、B、C、D两两用一段导线相连，可以证明只需3个电流计就可以推算出整个电路。请你编写程序求出：在保证每段导线的电流都可以直接或间接求出的前提下，安装电流计的总成本最小是多少？

输入格式

第一行是一个正整数\(T\)，表示测试数据的组数。
之后每组数据，第一行是两个正整数\(N,M\)；之后\(M\)行，每行包含3个整数\(a_i,b_i,c_i\)，表示在节点\(a_i\)和\(b_i\)之间有一条导线直接相连，在其上安装电流计的成本为\(c_i\)。输入保证\(1 \le a_i < b_i \le N\)，且任意两个不同节点之间最多有1条导线直接相连。

输出格式

每组数据输出一行。输出一个整数表示答案。

样例

Input

3
4 5
1 2 3
1 3 4
1 4 -5
2 3 5
2 4 1
4 6
1 2 1
1 3 2
1 4 3
2 3 5
2 4 6
3 4 7
6 10
1 2 32
1 4 52 
1 5 61
2 3 34
2 5 65
2 6 18
3 5 12
3 6 53
4 5 34
5 6 48

Output

-2
8
130

数据规模及约定

对于所有的测试文件：\(T \le 5\)
测试点1-2：\(N \le 7, \quad M \le 10\)
测试点3-5：\(N \le 120, \quad M \le 240\)
测试点6-8：\(N \le 10^5, \quad M \le 2 \times 10^5\)，所有\(c_i\)均为1
测试点9-10：\(N \le 10^5, \quad M \le 2 \times 10^5, \quad -10^9 \le c_i \le 10^9\)
时间限制1s，空间限制64MB。