Minimum Battery Capacity

As a busy programmer, Xiao Lan needs to travel between N cities frequently. The cities are numbered from 1 to N. There are M bidirectional highways, where the i-th highway connects city u_i and city v_i and consumes w_i units of battery.

You can fully charge the electric vehicle at the starting city and at any intermediate city you pass through. Xiao Lan wants to know the minimum battery capacity required so that, for any two distinct cities, there is a path (composed of one or more highways) where no single highway consumption exceeds the battery capacity. In other words, find the smallest X such that if you only consider highways with w_i \le X, the resulting graph is connected.

If it is impossible to travel between every pair of cities even when all highways are available, output -1.

Mathematical Formulation: Find the minimum X satisfying:

\[ \text{Graph } G_X = (V, \{(u,v) : w \le X\}) \text{ is connected}, \]

where the set of vertices is \(V = \{1, 2, \ldots, N\}\).

inputFormat

The first line contains two integers N and M (the number of cities and highways respectively).

Then follow M lines, each containing three integers u_i, v_i, and w_i representing a highway connecting city u_i and v_i with a battery consumption of w_i units.

outputFormat

Output one integer — the minimum battery capacity required so that every pair of cities is connected via a path whose every highway has a consumption not greater than this capacity. If it is impossible to travel between some pair of cities, output -1.

sample

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

4