您将获得一个由 $$$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$$$ 条边,因为它的权重较小。