题目描述

星港共有 $N$ 个停靠站，站点之间有 $M$ 条双向航道。每条航道会在某个整数时刻完成清障，清障完成后才可以通行。

你会得到每条航道连接的两个站点 $x,y$，以及它完成清障的时刻 $t$。请计算最早在哪一个时刻，任意两个站点之间都能通过已经清障的航道互相到达。

如果所有航道都完成清障后，仍然无法让所有站点连成一个整体，则输出 $-1$。

输入格式

第一行输入两个正整数 $N,M$。

接下来 $M$ 行，每行输入三个正整数 $x,y,t$，表示站点 $x$ 与站点 $y$ 之间的航道会在时刻 $t$ 完成清障。

输出格式

输出一行一个整数，表示所有站点首次两两可达的最早时刻；如果无法做到，输出 $-1$。

样例

5 6
1 2 8
2 3 4
3 4 7
4 5 6
1 5 10
2 5 5

8

样例说明

到时刻 $8$ 时，站点 $1$ 可以经由站点 $2$ 与其余所有站点连通；在此之前站点 $1$ 仍无法到达所有站点。

附件下载

数据范围

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