Mitty 是一位勇敢的冒险家，正在探索一个名为“深渊”（The Abyss）的神秘地下洞穴系统。深渊由 $n$ 条平行的垂直竖井和 $m$ 条水平通道组成。每条通道在同一深度连接恰好两条竖井。所有 $m$ 条通道的深度互不相同，令人惊讶的是，每条通道的正中间都藏有一份宝藏！

Mitty 可以选择任意一条竖井作为起点。他从所选竖井的顶部开始向下移动，并遵守以下规则：

• 他只能向下移动，不允许向上移动。
• 每当他遇到一条水平通道时，他必须立即进入该通道，并到达与之相连的竖井。
• 一旦他进入了一条水平通道，他就不能再返回。

这些通道中的宝藏具有不同的价值。Mitty 想要收集尽可能多价值的宝藏。请帮助他计算，当从其中一条竖井出发时，他所能收集到的宝藏的最大总价值。

输入格式

每个测试点包含多个测试用例。第一行包含测试用例的数量 $t$。接下来是每个测试用例的描述。

每个测试用例的第一行包含两个整数 $n$ 和 $m$，分别表示垂直竖井的数量和水平通道的数量。

接下来的 $m$ 行，每行包含三个整数 $x$、$y$ 和 $v$，表示一条位于某一深度的水平通道，它连接编号为 $x$ 和 $y$ 的竖井，且其中包含一份价值为 $v$ 的宝藏。

水平通道按从上到下的顺序给出。这意味着没有两条水平通道处于相同的深度。

输出格式

对于每个测试用例，输出一个整数，表示 Mitty 所能收集到的宝藏的最大总价值。

数据范围

• $1 \le t \le 20$
• $1 \le n \le 2 \times 10^5$
• $0 \le m \le 2 \times 10^5$
• $1 \le x < y \le n$
• $0 \le v \le 10^9$
• 保证所有测试用例中 $n$ 的总和不超过 $2 \times 10^5$。
• 保证所有测试用例中 $m$ 的总和不超过 $2 \times 10^5$。

样例

输入样例 1

1
3 3
1 2 3
2 3 4
1 3 9

输出样例 1

16

输入样例 2

2
5 8
1 4 5
1 3 4
1 3 2
1 3 9
2 4 1
1 3 2
2 3 0
1 5 6
7 2
5 6 16
5 7 4

输出样例 2

28
20