题目背景

一场地震摧毁了某区域内所有连接各村落的道路，工程队正在抓紧时间逐条修复。每条道路有一个预计修复完成的时间点。

题目描述

给定 $N$ 个村落和 $M$ 条双向道路，每条道路连接两个村落，并会在时间 $t$ 修复完毕。求最早在什么时刻，任意两个村落之间都能通过已修复的道路互相到达。若所有道路修完后仍有村落不连通，输出 $-1$。

输入格式

第 $1$ 行两个正整数 $N,M$。

接下来 $M$ 行，每行 $3$ 个正整数 $x,y,t$，表示连接村落 $x$ 和 $y$ 的道路将在时间 $t$ 修复完毕。

输出格式

若所有道路修复完毕后仍存在不连通的村落对，输出 $-1$；否则输出最早使所有村落连通的时刻。

样例

4 4
1 2 6
1 3 4
1 4 5
4 2 3

5

提示

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