Description

City S currently has two prisons, holding $N$ criminals numbered from $1$ to $N$. Their relationships are highly discordant. Many pairs of criminals have long-standing grudges and may break into conflict whenever conditions allow. We use the “resentment value” (a positive integer) to represent the hatred between two criminals; the larger the resentment value, the deeper their grudge. If two criminals with resentment value $c$ are held in the same prison, they will clash and cause a conflict event with impact $c$.

At the end of each year, the police department sorts all conflict events in the prisons by impact from large to small, and submits the list to Mayor Z of City S. The busy Mayor Z will only look at the impact of the first event in the list. If the impact is severe, he may consider replacing the police chief.

After carefully reviewing the conflicts among the $N$ criminals, the police chief feels great pressure. He plans to reassign the criminals between the two prisons to keep the impact of conflict events low, thereby protecting his position. Assume that if two criminals held in the same prison have a grudge, they will certainly clash at some point during the year.

How should the criminals be assigned to minimize the impact of the conflict event that Mayor Z sees? What is this minimum value?

Input Format

A single space separates two numbers in a line. The first line contains two positive integers $N, M$, representing the number of criminals and the number of pairs with grudges, respectively. Each of the next $M$ lines contains three positive integers $a_j, b_j, c_j$, indicating that criminals $a_j$ and $b_j$ have a grudge with resentment value $c_j$. It is guaranteed that $1 \le a_j < b_j \leq N$, $0 < c_j \leq 10^9$, and each pair of criminals appears at most once.

Output Format

Output a single line: the impact of the conflict event that Mayor Z sees. If no conflict occurs in the prisons this year, output 0.

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

3512

Hint

Input-output sample explanation:

The resentment values between criminals are shown in the left figure below. The right figure shows an assignment of criminals; the impact of the conflict event that the mayor sees is $3512$ (caused by criminals $2$ and $3$). No other assignment is better than this one.

Constraints

• For $30\%$ of the testdata, $N \leq 15$.
• For $70\%$ of the testdata, $N \leq 2000$, $M \leq 50000$.
• For $100\%$ of the testdata, $N \leq 20000$, $M \leq 100000$.

Translated by ChatGPT 5