I. Rebellious Edge
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Given a directed graph where each edge has a nonnegative weight, and a root vertex $$$r$$$, the directed minimum spanning tree problem asks to choose a subset of edges such that:

  • Using the selected edges, there exists a directed path from $$$r$$$ to $$$u$$$ for every vertex $$$u$$$.
  • The chosen subset of edges forms a spanning tree of the graph if the directions of the edges are ignored.
  • The total weight of the chosen edges is minimized.

Although there exist efficient algorithms for computing the directed minimum spanning tree, we look at a simple special case in this problem. Given is a directed graph with $$$n$$$ vertices and $$$m$$$ directed edges. The vertices are indexed $$$1 \ldots n$$$. All edges, except for exactly one, are directed from the vertex with the smaller index to the vertex with the bigger index. There are no parallel edges, i.e. for every pair of vertices $$$(u, v)$$$, there is at most one edge $$$u \to v$$$. Find the directed minimum spanning tree, with root vertex 1.

Input

The first line contains one integer $$$t$$$ ($$$1 \le t \le 10^5$$$) — the number of test cases. $$$t$$$ test cases follow. Each test case is described as follows.

The first line of the test case consists of two integers $$$n$$$ and $$$m$$$ ($$$3 \le n \le 2 \cdot 10^5$$$, $$$n - 1 \le m \le 5 \cdot 10^5$$$). The following $$$m$$$ lines each consist of three integers $$$u$$$, $$$v$$$ and $$$w$$$, denoting an edge $$$u \to v$$$ with weight $$$w$$$ ($$$1 \le u, v \le n$$$, $$$u \ne v$$$, $$$0 \le w \le 10^9$$$). For all but one of these lines $$$u \lt v$$$.

It is guaranteed that the sum of $$$n$$$ over all test cases doesn't exceed $$$2 \cdot 10^5$$$ and the sum of $$$m$$$ over all test cases doesn't exceed $$$5 \cdot 10^5$$$.

The tests are constructed in such a way that a directed spanning tree always exists.

Output

For each test case, print the answer on a separate line — a single integer, the total weight of edges in the directed minimum spanning tree.

Example
Input
3
5 6
1 2 4
1 3 2
2 3 0
3 4 1
4 5 1
5 2 1
4 4
1 2 4
1 3 6
1 4 8
4 2 1000000
3 3
1 2 100
2 1 10
2 3 1000
Output
5
18
1100
Note

The figure below illustrates the first example test case. The solid edges are the ones in the directed minimum spanning tree. Notice that if we didn't use the backwards edge, the total weight would have to be at least 6.

In the second example, the backwards edge has a very high weight, so there is no point in considering it.

Notice that although the statement guarantees that there are no parallel edges, antiparallel edges (such as seen in the third example) are allowed.