Problem Description

City S has two prisons, holding a total of N prisoners numbered 1 to N.

The relationships between them are naturally very hostile.

Many prisoners have long-standing grievances, and if conditions allow, conflicts may erupt at any time.

We use a "hostility value" (a positive integer) to represent the degree of hatred between two prisoners. The higher the hostility value, the more deep-seated the grievance between them.

If two prisoners with hostility value c are held in the same prison, they will clash, causing a conflict event with impact c.

At the end of each year, the police department compiles a list of all conflict events in the prisons during the year, sorted by impact in descending order, and reports it to Mayor Z of City S.

Mayor Z, busy with official duties, only looks at the impact value of the first event on the list. If it is unacceptably high, he considers replacing the police chief.

After thoroughly examining the conflict relationships among the N prisoners, the police chief feels immense pressure.

He plans to reassign the prisoners between the two prisons to ensure that any conflict events have minimal impact, thereby keeping his job.

Assuming that any two prisoners in the same prison who have hatred will inevitably clash at some point during the year, how should the prisoners be assigned so that the impact value seen by Mayor Z is minimized? What is this minimum value?

Input Format
The first line contains two positive integers N and M, representing the number of prisoners and the number of hostile prisoner pairs.

The next M lines each contain three positive integers a_j, b_j, c_j, indicating that prisoners a_j and b_j have a hostility value c_j.

The data guarantees 1 ≤ a_j < b_j ≤ N, 0 < c_j ≤ 10⁹, and each prisoner pair appears only once.

Output Format
Output a single integer, the impact value of the conflict event seen by Mayor Z.

If no conflict event occurs in the prisons during the year, output 0.

Data Range
N ≤ 20000, M ≤ 100000

Input Sample:

4 6
1 4 2534
2 3 3512
1 2 28351
1 3 6618
2 4 1805
3 4 12884

Output Sample:

3512