P1111 Repairing Roads

A 地区在地震过后，连接所有村庄的公路都造成了损坏而无法通车。政府派人修复这些公路。

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).

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$.

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.

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