Minimize Maximum Conflict Influence

S City has two prisons and N criminals numbered from 1 to N. Certain pairs of criminals harbor deep-seated grudges quantified by a positive integer called the enmity value \(c\). If two criminals with enmity \(c\) are placed in the same prison, they will eventually have a conflict event with influence \(c\).

Every year, the police list all conflict events in descending order of their influence and report only the first (i.e. the one with the highest influence) to Mayor Z. Concerned that a high-impact event might force him to replace the police chief, the chief wants to reassign the criminals between the two prisons so that the influence of the worst (maximum) conflict event is minimized.

Formally, you are given a graph of N vertices (criminals) and M edges. Each edge \((u,v)\) has an associated positive weight \(c\) (the enmity value). When both endpoints of an edge are assigned to the same prison, a conflict with influence \(c\) will occur. Let \(M_\text{conflict}\) be the maximum influence among all conflict events that occur. The goal is to find an assignment of criminals into two prisons so that \(M_\text{conflict}\) is minimized. Equivalently, find the minimum \(X\) such that there exists a partition where every edge with \(c > X\) has its endpoints in different prisons. Note that if the criminals can be separated such that no edge remains inside a prison then the answer is \(0\).

Input includes all formulas in \(\LaTeX\) format.

inputFormat

The first line contains two integers \(N\) and \(M\), representing the number of criminals and the number of enmity relationships, respectively. Each of the following \(M\) lines contains three positive integers \(u\), \(v\) and \(c\), indicating that criminals \(u\) and \(v\) share an enmity value \(c\).

outputFormat

Output a single integer, which is the minimum possible maximum conflict influence achievable by an optimal assignment.

sample

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

0