Description

Given the number of villages $N$ and the number of roads $M$ in region A. The roads are bidirectional. You are told which two villages each road connects and when this road will be completed. Find the earliest time when any two villages can travel between each other, i.e., the earliest time when for any pair of villages there exists at least one completed path (possibly consisting of multiple roads).

Input Format

The first line contains two positive integers $N, M$.

Then the next $M$ lines follow. Each line contains three positive integers $x, y, t$, indicating that this road connects villages $x$ and $y$, and it will be completed at time $t$.

Output Format

If, after all roads are completed, there still exist two villages that cannot travel between each other, output $-1$. Otherwise, output the earliest time when any two villages can travel between each other.

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

5

Hint

$1\leq x, y\leq N \le 10 ^ 3$, $1\leq M, t \le 10 ^ 5$.

Translated by ChatGPT 5