说明

米蒂是一位勇敢的冒险家，正在探索一个名为“深渊”的神秘地下洞穴系统。深渊由 $n$ 条垂直的竖井和 $m$ 条水平的隧道组成。每条隧道恰好连接同一深度上的两条竖井。所有 $m$ 条隧道的深度各不相同，而且令人惊奇的是，每条隧道的正中央都有一份宝藏！

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

• 他只能向下移动，不允许向上移动。
• 每当遇到一条水平隧道时，他 必须 立即进入这条隧道，并到达与之相连的另一条竖井。
• 一旦进入一条水平隧道，就无法原路返回。

这些隧道中的宝藏具有不同的价值。米蒂希望尽可能多地收集宝藏。请帮助他计算，从某条竖井出发时，他最多能收集到的宝藏总价值。

输入格式

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

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

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

水平隧道按照从上到下的顺序给出，这意味着不会有两条水平隧道处于同一深度。

输出格式

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

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

16

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

28
20

提示

• $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$。

翻译由 DeepSeek V3.2 完成