Earliest Connection Time

Problem Statement:

Given (N) villages and (M) bidirectional roads in region A. Each road connects two villages and is repaired (completed) at a specified time (t). Determine the earliest time such that any two villages are connected by a series of completed roads. In other words, find the minimum time when the graph becomes connected (i.e. there exists a path between any two villages).

Note: It is guaranteed that eventually all villages will be connected.

inputFormat

Input Format:

The first line contains two integers (N) and (M), representing the number of villages and the number of roads, respectively. Each of the following (M) lines contains three integers (u), (v), and (t) indicating that a road connecting village (u) and village (v) will be completed at time (t).

Note: Villages are numbered from 1 to (N).

outputFormat

Output Format:

Output a single integer representing the earliest time when the network becomes connected (i.e. there exists a path between any two villages via roads that are completed by that time).

sample

3 3
1 2 5
2 3 8
1 3 10

8