A swarm has n sensors, numbered 1 through n. There are m wireless links; link i connects two sensors and switches on at time t_i, staying on afterward. At any given time, two sensors are connected if there is a chain of already-switched-on links between them.
Find the earliest time at which every sensor is connected to every other (the whole swarm forms one connected group). If the swarm never becomes fully connected, report -1.
Input format
- Line 1: two integers
nandm. - Next
mlines: three integers , , (sensors 1-indexed, ), a link between and that switches on at time . Several links may share the same time.
Output format
A single integer: the earliest time the swarm is fully connected, or -1.
Constraints
- 2 <= n <= 100000
- 0 <= m <= 200000
- 1 <= u, v <= n and u != v
- 1 <= t <= 1000000000