给定一个每条边都有非负权值的有向图和一个根节点 $r$，有向最小生成树问题要求选择一个边集，使得：

• 使用所选边集，对于每个顶点 $u$，都存在一条从 $r$ 到 $u$ 的有向路径。
• 如果忽略边的方向，所选边集构成该图的一棵生成树。
• 所选边的总权值最小。

尽管存在计算有向最小生成树的高效算法，但我们在此问题中考虑一个简单的特殊情况。给定一个具有 $n$ 个顶点和 $m$ 条有向边的有向图。顶点编号为 $1 \dots n$。除恰好一条边外，所有边均从编号较小的顶点指向编号较大的顶点。图中不存在平行边，即对于每一对顶点 $(u, v)$，最多只有一条边 $u \to v$。请找出以顶点 $1$ 为根的有向最小生成树。

输入格式

第一行包含一个整数 $t$ ($1 \le t \le 10^5$)，表示测试用例的数量。接下来是 $t$ 个测试用例。每个测试用例描述如下：

第一行包含两个整数 $n$ 和 $m$ ($3 \le n \le 2 \cdot 10^5, n - 1 \le m \le 5 \cdot 10^5$)。 接下来的 $m$ 行，每行包含三个整数 $u, v$ 和 $w$，表示一条从 $u$ 指向 $v$ 的边，权值为 $w$ ($1 \le u, v \le n, u \neq v, 0 \le w \le 10^9$)。除其中一行外，其余所有行均满足 $u < v$。

保证所有测试用例的 $n$ 之和不超过 $2 \cdot 10^5$，且所有测试用例的 $m$ 之和不超过 $5 \cdot 10^5$。 测试数据的构造保证有向生成树一定存在。

输出格式

对于每个测试用例，在单独的一行中输出答案——一个整数，即有向最小生成树中边的总权值。

样例

输入 1

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

输出 1

5
18
1100

说明

下图展示了第一个样例测试用例。实线边为有向最小生成树中的边。注意，如果我们不使用那条反向边，总权值至少为 $6$。

在第二个样例中，反向边的权值非常大，因此没有考虑它的必要。 注意，尽管题目保证不存在平行边，但允许存在反向平行边（如第三个样例所示）。