CF1423B.Valuable Paper

The pandemic is upon us, and the world is in shortage of the most important resource: toilet paper. As one of the best prepared nations for this crisis, BubbleLand promised to help all other world nations with this valuable resource. To do that, the country will send airplanes to other countries carrying toilet paper.

In BubbleLand, there are $N$ toilet paper factories, and $N$ airports. Because of how much it takes to build a road, and of course legal issues, every factory must send paper to only one airport, and every airport can only take toilet paper from one factory.

Also, a road can't be built between all airport-factory pairs, again because of legal issues. Every possible road has number $d$ given, number of days it takes to build that road.

Your job is to choose $N$ factory-airport pairs, such that if the country starts building all roads at the same time, it takes the least amount of days to complete them.

疫情来袭，全球正面临一种最重要资源的短缺：卫生纸。作为为此次危机准备最充分的国家之一，泡泡国（BubbleLand）承诺向世界各国提供这种宝贵资源。为此，该国将派遣飞机向其他国家运送卫生纸。

在泡泡国，共有 $N$ 座卫生纸工厂和 $N$ 座机场。由于修建道路成本高昂，且受法律限制，每座工厂至多只能向一座机场运送卫生纸，且每座机场也仅能接收来自一座工厂的卫生纸。

此外，并非所有工厂与机场之间都允许修建道路（同样出于法律限制）。每条可能修建的道路均被赋予一个数值 $d$，表示修建该道路所需的天数。

你的任务是选出 $N$ 对工厂-机场组合，使得若全国同时开始修建所有选定的道路，则完成全部道路建设所需的总天数最少。

The first line contains two integers $N$ $(1 \leq N \leq 10^4)$ - number of airports/factories, and $M$ $(1 \leq M \leq 10^5)$ - number of available pairs to build a road between.

On next $M$ lines, there are three integers $u$, $v$ $(1 \leq u,v \leq N)$, $d$ $(1 \leq d \leq 10^9)$ - meaning that you can build a road between airport $u$ and factory $v$ for $d$ days.

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

If there are no solutions, output -1. If there exists a solution, output the minimal number of days to complete all roads, equal to maximal $d$ among all chosen roads.

如果没有解，输出 -1。如果存在解，输出完成所有道路所需的最少天数，该值等于所有选定道路中最大的 $d$。