Edge Reverse

题意翻译

你将得到一个有 $n$ 个节点和m条有向边的加权有向图，其中第 $i$ 条边的权重为 $w_i$（ $1\le i\le m$ ）。 你需要反转该图的一些边，使图中至少有一个能够到达图中其他节点的节点。这些反转的代价等于所有需要反转的边的最大权值。如果不需要反转任何边，那么代价等于 $0$ 。 保证不存在自环或重边。 请找到完成任务所需的最小成本。如果没有解决方案，打印一个整数 $-1$ 。

题目描述

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 $ .

输入输出格式

输入格式

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 $ .

输出格式

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

输入输出样例

输入样例 #1

4
2 1
1 2 3
5 4
1 2 10
2 3 10
3 1 10
4 5 10
4 5
1 2 10000
2 3 20000
1 3 30000
4 2 500
4 3 20
4 5
1 2 10000
2 3 20000
1 3 30000
4 2 5
4 3 20

输出样例 #1

0
-1
20
5

说明

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.

题目大意：
你将得到一个有n个节点和m条有向边的加权有向图，其中第i条边的权重为$w_i$（$1 \le i \le m$）。需要反转一些边，使图中至少有一个能够到达图中其他节点的节点。反转的代价等于所有需要反转的边的最大权值。如果不需要反转任何边，那么代价为$0$。图中不存在自环或重边。求完成任务所需的最小成本。如果没有解决方案，输出$-1$。

输入输出数据格式：
每个测试包含多个测试案例。第一行包含测试案例数$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行，每行包含3个整数$u$、$v$、$w$（$1 \le u, v \le n$，$1 \le w \le 10^9$），表示从$u$到$v$权重为$w$的一条边。保证没有边连接一个顶点到自身，也没有两条边共享相同的起点和终点。所有测试案例的$n$和$m$之和不超过$2 \cdot 10^5$。

对于每个测试案例，输出完成任务的最低成本。如果没有解决方案，输出$-1$。题目大意： 你将得到一个有n个节点和m条有向边的加权有向图，其中第i条边的权重为$w_i$（$1 \le i \le m$）。需要反转一些边，使图中至少有一个能够到达图中其他节点的节点。反转的代价等于所有需要反转的边的最大权值。如果不需要反转任何边，那么代价为$0$。图中不存在自环或重边。求完成任务所需的最小成本。如果没有解决方案，输出$-1$。 输入输出数据格式： 每个测试包含多个测试案例。第一行包含测试案例数$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行，每行包含3个整数$u$、$v$、$w$（$1 \le u, v \le n$，$1 \le w \le 10^9$），表示从$u$到$v$权重为$w$的一条边。保证没有边连接一个顶点到自身，也没有两条边共享相同的起点和终点。所有测试案例的$n$和$m$之和不超过$2 \cdot 10^5$。 对于每个测试案例，输出完成任务的最低成本。如果没有解决方案，输出$-1$。