题目背景

A 地区发生地震，村庄之间的公路全部受损，车辆无法通行。政府已经派出施工人员修复这些公路，每条公路的修复时间已知。

题目描述

A 地区有 $N$ 个村庄、 $M$ 条双向公路。现在知道每条公路连接哪两个村庄，以及它在什么时刻修复完毕。到达修复时刻后，这条公路就可以通车。

求最早的一个时刻，使任意两个村庄间都能往来。路程可以由多条已经修复的公路组成。

第一行是两个正整数 $N,M$ ，分别表示村庄数与公路数。以下 $M$ 行各给出三个正整数 $x,y,t$ ，表示连接村庄 $x$ 与 $y$ 的公路在时刻 $t$ 修好。

输出最早的连通时刻。若全部公路修复后仍无法使所有村庄连通，输出 -1。

$1\le x,y\le N\le10^3$ ， $1\le M,t\le10^5$ 。