In 2021, you set up your own company called Rainbow Island Trading Company and you want to trade with n countries in the world.
Due to financial reasons, you have only established n factories, but you want to trade with all n countries in the world. So every factory must send product to only one country, and every country can only take product from one factory.
When everything is ready, you find that there is no road between the factory and the country where you need to trade. Unfortunately, you are told that you can only build some roads among the m planned roads and the construction time of each road may be different.
Since you want to start trading as soon as possible, so your task is to calculate at least how much time it will take to build roads if you start building all roads at the same time.
输入格式
The first line contains two integers $n,m(1\leq n\leq 10^4,1\leq m\leq 10^5)$ —— the number of factories/countries and planned roads respectively.
Next $m$ lines, there are three integers $u,v(1\leq u,v\leq n)$ and $t(1\leq t\leq 10^9)$ —— meaning that you can build a road between factory $u$ and country $v$ for $t$ days.
输出格式
If there are no solutions, output -1, otherwise output otherwise output an integer to indicate at least the required time.
