CF1777E.Edge Reverse

You will be given a weighted directed graph of $n$ nodes and $m$ directed edges, where the $i$-th edge has a weight of $w_i$ ($1 \le i \le m$).

You need to reverse some edges of this graph so that there is at least one node in the graph from which every other node is reachable. The cost of these reversals is equal to the maximum weight of all reversed edges. If no edge reversal is required, assume the cost to be $0$.

It is guaranteed that no self-loop or duplicate edge exists.

Find the minimum cost required for completing the task. If there is no solution, print a single integer $-1$.

你将得到一个包含 $n$ 个节点和 $m$ 条有向边的带权有向图，其中第 $i$ 条边（$1 \le i \le m$）的权重为 $w_i$。

你需要翻转该图中的若干条边，使得图中至少存在一个节点，从该节点出发可以到达图中所有其他节点。这些翻转操作的代价等于所有被翻转边中权重的最大值。若无需翻转任何边，则代价视为 $0$。

保证图中不存在自环或重边。

请找出完成该任务所需的最小代价。若无解，请输出单个整数 $-1$。

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10^5$). The description of the test cases follows.

Each test case begins with a line containing two integers $n$ and $m$ ($2 \le n \le 2 \cdot 10^5$, $1 \le m \le 2 \cdot 10^5$) — the number of nodes in the graph and the number of edges in the graph.

The next $m$ lines of each test case contain $3$ integers each — $u$, $v$, $w$ ($1 \le u, v \le n$, $1 \le w \le 10^9$), indicating an edge from $u$ to $v$ with a weight of $w$. It is guaranteed that no edge connects a vertex to itself, and no pair of edges share the same origin and destination simultaneously.

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

每个测试包含多个测试用例。第一行包含测试用例的数量 $t$（$1 \le t \le 10^5$）。随后是各测试用例的描述。

每个测试用例以一行开始，该行包含两个整数 $n$ 和 $m$（$2 \le n \le 2 \cdot 10^5$，$1 \le m \le 2 \cdot 10^5$）—— 分别表示图中节点的数量和边的数量。

每个测试用例的接下来 $m$ 行，每行包含三个整数 $u$、$v$、$w$（$1 \le u, v \le n$，$1 \le w \le 10^9$），表示一条从 $u$ 到 $v$、权重为 $w$ 的有向边。保证不存在连接顶点到其自身的边，且不存在两条边具有完全相同的起点和终点。

保证所有测试用例中 $n$ 的总和与 $m$ 的总和均不超过 $2 \cdot 10^5$。

For each test case, output the minimum cost. If there is no solution, print $-1$.

对于每个测试用例，输出最小代价。若无解，则输出 $-1$。

In the first test case, an edge exists from $1$ to $2$, so all nodes are reachable (from $1$).

In the second test case, no nodes are reachable from any node no matter what edges we reverse, so the answer is $-1$.

In the third test case, reversing the $4$-th or $5$-th edge allows all nodes to be reachable from $1$. We choose the $5$-th edge here because its weight is smaller.

在第一个测试用例中，存在一条从节点 $1$ 到节点 $2$ 的边，因此所有节点均可从节点 $1$ 到达。

在第二个测试用例中，无论我们翻转哪些边，都不存在从任意节点出发可到达的所有节点，因此答案为 $-1$。

在第三个测试用例中，翻转第 $4$ 条或第 $5$ 条边均可使所有节点从节点 $1$ 可达。此处我们选择第 $5$ 条边，因为其权重更小。