疫情来袭,世界短缺最重要的资源:卫生纸。作为应对这场危机准备最充分的国家之一,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