描述

方块鸟大陆上有 $N$ 个区域，他们之间是无人居住、魔物占领的荒野，一般的商队都需要付出高昂的费用去雇佣保镖来确保旅途安全。为此，方块鸟大陆的工会首领们决定在荒野上修筑安全商路来加强区域之间的连接，让旅行和商品交换变得更加容易。

经过讨论，工会首领计划修建 $M$ 条商路，每条商路连接两个区域。由于区域之间荒野魔物强弱不等、距离也不一，每条商路的修筑时间都不一样。小方小块小鸟知道，一旦安全商路修建完毕，方块鸟大陆上的贸易往来将会发生很大变化，他们想要成立商会去大赚一笔。

现在你已经拿到了全部的商路信息，你需要帮小方小块小鸟弄清楚，最早在什么时候，整个方块鸟大陆的任意两个区域之间，都可以通过安全商路来通行（可以利用多条商路中转），无需雇佣保镖。

输入输出格式

第一行为两个以空格隔开的正整数 $N$ 、 $M$ ，表示区域数量和计划的安全商路数量。 ( $1 ≤ N ≤ 1000, 1 ≤ M ≤ 100,000$ )

随后 $M$ 行，每行三个以空格分割的正整数 $x , y, t$ ，表示 x 区域和 y 区域之间的安全商路最早在t时间完工。 ( $1 ≤ x, y ≤ 1000, 1 ≤ t ≤ 100,000$ )

一行，表示任意两个区域之间都可以通过安全商路通行的最早时间。如果这个商路计划建成以后，仍然有些区域之间需要经过荒野，则输出-1，表示成立商会还是言之过早。

在第5个时刻，1-3、1-2、2-4 都修好了，任意两个区域都可以通过安全商路进行贸易。