CF1777E Edge Reverse

给定一个有 $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$ 行，每行包含三个整数 $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$ 到 $2$ 的边，因此所有节点都可以从 $1$ 到达。 在第二个测试用例中，无论如何反转边，都无法使任意节点可以到达所有节点，因此答案为 $-1$。 在第三个测试用例中，反转第 $4$ 条或第 $5$ 条边都可以使所有节点从 $1$ 出发可达。此处选择反转第 $5$ 条边，因为其权值更小。 由 ChatGPT 4.1 翻译