← 返回题目列表

Codeforces · 1777/E

E. 边沿反转

中文机器翻译题面 查看原题

您将获得一个由 $$$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$$$。

示例

输入 #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

注意

在第一个测试用例中,从 $$$1$$$ 到 $$$2$$$ 存在一条边,因此所有节点都是可达的(从 $$$1$$$)。

在第二个测试用例中,无论我们反转什么边,都无法从任何节点到达任何节点,因此答案是 $$$-1$$$。

在第三个测试用例中,反转第 $$$4$$$ 或第 $$$5$$$ 边允许从 $$$1$$$ 到达所有节点。我们在这里选择第 $$$5$$$ 条边,因为它的权重较小。