Description

Mitty is a brave adventurer exploring a mysterious underground cave system known as The Abyss. The Abyss is composed of $n$ parallel vertical shafts and $m$ horizontal tunnels. Each tunnel connects exactly two shafts at the same depth. All $m$ tunnels have distinct depths, and surprisingly, there is a treasure in the middle of every tunnel!

Mitty can pick any shaft to start with. He moves downward from the top of the chosen shaft, obeying the following rules:

• He can only move downward, going upward is not allowed.
• Whenever he encounters a horizontal tunnel, he must enter it immediately and will arrive at the connected shaft.
• Once he enters a horizontal tunnel, he cannot go back.

These treasures in the tunnels have various values. Mitty wants to collect as much treasure as possible. Please help him calculate the maximum total value of treasures he can collect when starting from one of the shafts.

Input Format

Each test contains multiple test cases. The first line contains the number of test cases $t$. The description of the test cases follows.

The first line contains two integers $n$ and $m$, representing the number of vertical shafts and horizontal tunnels, respectively.

Each of the following $m$ lines contains three integers $x$, $y$ and $v$, representing a horizontal tunnel at a certain depth that connects shafts numbered $x$ and $y$, and contains a treasure worth $v$.

The horizontal tunnels are given from top to bottom. This implies that no two horizontal tunnels situated at the same depth.

Output Format

For each test case, print a single integer, representing the maximum total value of treasures Mitty can collect.

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

Hint

• $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$
• It is guaranteed that the sum of $n$ over all test cases does not exceed $2 \times 10^5$.
• It is guaranteed that the sum of $m$ over all test cases does not exceed $2 \times 10^5$.