257. detention of offenders

S There are two prisons in the city , There is a total of N Criminals , The numbers are 1∼N.

The relationship between them is naturally very disharmonious .

Many criminals even have a long history of resentment , If the objective conditions are met, conflicts may break out at any time .

We use it “ Resentment value ”（ A positive integer value ） To show the level of hatred between two criminals , The greater the value of resentment , The more resentment there is between the two criminals .

If two of them have a complaint value of c Of the criminals were held in the same prison , There will be friction between them , And the influence is c The conflict of .

At the end of each year , The police department will make a list of all the conflicts in prison this year, from the largest to the smallest , Then report to S city Z The mayor .

Busy with business Z The mayor will only look at the impact of the first event on the list , If the impact is bad , He will consider replacing the chief of Police .

In a detailed investigation of N After the contradiction between the criminals , The chief of police felt a lot of pressure .

He is going to redistribute the criminals in two prisons , In order to produce less impact of Conflict Events , So as to keep your own black hat .

Suppose that as long as there is hatred between two criminals in the same prison , Then they must have friction sometime every year .

that , How should criminals be distributed , Can we make Z The conflict the mayor saw had the least impact ？ What's the minimum ？

Input format

The first line is two positive integers N and M, It shows the number of criminals and the number of criminals with hatred .

Next M Three positive integers per line aj,bj,cj, Express aj Number and bj There's hatred between criminals , Its complaint value is cj.

Output format

The output, 1 That's ok , by Z The impact of the conflict the mayor saw .

If there is no conflict in prison this year , Please export 0.

Data range

N≤20000,M≤100000

sample input ：

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

sample output ：

3512

Code ：

/* ( Two points , To judge a bipartite graph by coloring ) O((N+M)logC)  Take the criminal as a point , The hate relationship between criminals is regarded as the undirected edge between points , The weight of the edge is the hate value between criminals .  Then the original problem becomes ： Divide all points into two groups , Make the maximum weight of the inner edges of each group as small as possible .  We are  [0,109]  Enumerate the maximum edge weights between  limit, When  limit  After fixing , The rest of the problem is ：  Judge whether all points can be divided into two groups , Make the ownership value greater than  limit  All the sides are between the groups , Not in the group . That is, it is judged by all points and the ownership value is greater than  limit  Whether the new graph formed by the edges of is a bipartite graph .  We can judge a bipartite graph by coloring , The time complexity is  O(N+M), among  N  It's points ,M  It's the number of sides   To speed up the algorithm , Let's consider whether we can use binary enumeration  limit,  Suppose that the minimum value of the final maximum edge weight is  Ans:  So when  limit∈[ans,109]  when , All edge weights are greater than  limit  The edge of , It must be that all edge weights are greater than Ans  A subset of the edges of , Therefore, the new graph is also a bipartite graph .  When  limit∈[0,ans−1]  when , because ans  Is the minimum value that a new graph can form a bipartite graph , Therefore, by more than  limit  The new graph formed by the edges of must not be a bipartite graph .  So the whole interval has the property of two segments , The dividing point can be divided in two  ans  Value . */

#include <bits/stdc++.h>
using namespace std;
const int N = 20010, M = 200010;

int n, m;
int h[N], e[M], w[M], ne[M], idx;
int color[N];

void add(int a, int b, int c)
{
    
    e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx++;
}
bool dfs(int u, int c, int mid)
{
    
    color[u] = c;
    for (int i = h[u]; ~i; i = ne[i])
    {
    
        int j = e[i];
        if (w[i] <= mid)
            continue;
        if (color[j])
        {
    
            if (color[j] == c)
                return false;
        }
        else if (!dfs(j, 3 - c, mid))
            return false;
    }
    return true;
}

bool check(int mid)
{
    
    memset(color, 0, sizeof color);
    for (int i = 1; i <= n; i++)
        if (!color[i])
            if (!dfs(i, 1, mid))
                return false;
    return true;
}

int main()
{
    
    scanf("%d%d", &n, &m);
    memset(h, -1, sizeof h);

    while (m--)
    {
    
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);
        add(a, b, c), add(b, a, c);
    }

    int l = 0, r = 1e9;
    while (l < r)
    {
    
        int mid = r + l >> 1;
        if (check(mid))
            r = mid;
        else
            l = mid + 1;
    }

    printf("%d\n", r);

    return 0;
}