← 返回题目列表

Codeforces · 1423/B

B. 有价值的论文

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

疫情来袭,世界短缺最重要的资源:卫生纸。作为应对这场危机准备最充分的国家之一,BubbleLand 承诺利用这一宝贵资源帮助世界上所有其他国家。为此,该国将派飞机前往其他国家运送卫生纸。

在BubbleLand中,有$$$N$$$卫生纸工厂和$$$N$$$机场。由于修一条路需要多少钱,当然还有法律问题,每个工厂只能向一个机场运送纸张,每个机场只能从一个工厂获取卫生纸。

此外,由于法律问题,无法在所有机场-工厂对之间修建道路。每条可能的道路都给出了数字 $$$d$$$,即修建该道路所需的天数。

你的工作是选择 $$$N$$$ 工厂-机场对,这样,如果该国同时开始修建所有道路,则完成它们所需的天数最少。

输入

第一行包含两个整数 $$$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$$$。

示例

输入 #1

3 5
1 2 1
2 3 2
3 3 3
2 1 4
2 2 5

输出 #1

4