CF1423B Valuable Paper

疫情来袭，世界正面临最重要资源——厕纸的短缺。作为为这场危机准备最充分的国家之一，BubbleLand 承诺将用这种宝贵的资源帮助世界上所有其他国家。为此，该国将派遣飞机向其他国家运送厕纸。 在 BubbleLand，有 $N$ 个厕纸工厂和 $N$ 个机场。由于修建道路的成本以及法律问题，每个工厂只能向一个机场发送厕纸，每个机场也只能从一个工厂接收厕纸。 同样地，由于法律问题，并不是所有的机场-工厂对之间都可以修建道路。每一条可建道路都有一个数字 $d$，表示修建这条道路所需的天数。 你的任务是选择 $N$ 对工厂-机场，使得如果国家同时开始修建所有道路，完成所有道路所需的天数最少，即所有被选中道路中 $d$ 的最大值最小。

第一行包含两个整数 $N$ $(1 \leq N \leq 10^4)$ —— 机场和工厂的数量，以及 $M$ $(1 \leq M \leq 10^5)$ —— 可以修建道路的对数。 接下来的 $M$ 行，每行包含三个整数 $u$、$v$ $(1 \leq u,v \leq N)$、$d$ $(1 \leq d \leq 10^9)$，表示可以在机场 $u$ 和工厂 $v$ 之间修建一条道路，修建时间为 $d$ 天。

如果无解，输出 $-1$。如果存在解，输出完成所有道路所需的最少天数，即所选道路中最大的 $d$ 的最小值。

由 ChatGPT 4.1 翻译