You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

Background

使徒来袭 ! ! !

Description

明日香正在被使徒追击$，$她逃到了一个名为 "深渊 "的神秘地下洞穴系统。深渊由 $n$ 个平行竖井和 $m$ 个水平隧道组成。每条隧道都在同一深度正好连接两个竖井。所有 $m$ 隧道都有不同的深度，令人惊讶的是，每条隧道中间都有一个能摧毁使徒"$AT$立场"的宝藏！

明日香可以选择任何一个竖井开始。她从所选竖井的顶部向下移动，并遵守以下规则$：$

她只能向下移动，不能向上。 每当遇到水平隧道时，她必须立即进入隧道，并到达相连的竖井。 一旦进入水平隧道，就不能返回。 隧道中的宝藏价值不一。明日香想收集尽可能多的宝藏以求击败使徒。请帮她计算一下，当她从一个竖井开始时，可以收集到的宝藏的最大总价值。

Format

Input

每个测试包含多个测试用例。第一行包含测试用例的数量$t$ 。测试用例说明如下。

第一行包含两个整数 $n$ 和 $m$ ，分别代表竖井和水平隧道的数量。

接下来的每行 $m$ 包含三个整数 $x$， $y$ 和 $v$ ，分别代表一定深度的水平隧道，连接编号为 $x 和 y$ 的竖井，并包含价值 $v$ 的宝藏。

水平隧道从上到下依次排列。这意味着没有两条水平隧道位于同一深度。

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

Output

为每个测试用例打印一个整数，代表明日香能收集到的宝物的最大总值。

Samples

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

Limitation

Time limit per test : 1000ms

Memory limit per test : 256 MiB