#include<bits/stdc++.h>
using namespace std;

const int maxn=3010;
const int maxm=2e5+5;
const int INF=0x3f3f3f3f;

int FIR[maxn],TO[maxm],NEXT[maxm],W[maxm],tote;
bool vis[maxn];
int F[maxn],link[maxn],wage[maxn];
int n,m;

void add(int u,int v,int w)
{
    TO[tote]=v;
    W[tote]=w;
    NEXT[tote]=FIR[u];
    FIR[u]=tote++;

    TO[tote]=u;
    W[tote]=w;
    NEXT[tote]=FIR[v];
    FIR[v]=tote++;
}
int Find(int x)
{
    return x==F[x]?x:F[x]=Find(F[x]);
}
void Join(int u,int v)
{
    int p=u;
    while(link[p]!=-1)p=link[p];
    link[p]=v;
    F[v]=u;
}
int MinCut(int cnt,int &s,int &t)
{
    memset(wage,0,sizeof wage);
    memset(vis,false,sizeof vis);
    priority_queue< pair<int,int> >q;
    t=1;
    while(--cnt)
    {
        vis[s=t]=true;
        for(int u=s;u!=-1;u=link[u])
        {
            for(int p=FIR[u];p!=-1;p=NEXT[p])
            {
                int v=Find(TO[p]);
                if(!vis[v])
                    q.push(make_pair(wage[v]+=W[p],v));
            }
        }
        t=0;
        while(!t)
        {
            if(q.empty())return 0;
            pair<int,int> pa=q.top();q.pop();
            if(wage[pa.second]==pa.first)
                t=pa.second;
        }
    }
    return wage[t];
}
int Stoer_Wagner()
{
    int res=INF;
    for(int i=n,s,t;i>1;i--)
    {
        res=min(res,MinCut(i,s,t));
        if(res==0)break;
        Join(s,t);
    }
    return res;
}
void init()
{
    tote=0;
    for(int i=1;i<=n;i++)FIR[i]=link[i]=-1,F[i]=i;
}
int main()
{
    while(scanf("%d%d",&n,&m)!=EOF)
    {
        init();
        for(int i=0,u,v,w;i<m;i++)
        {
            scanf("%d%d%d",&u,&v,&w);
            add(u,v,w);
        }
        printf("%d\n",Stoer_Wagner());
    }
    return 0;
}