#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstdlib>
#include<algorithm>
#include<cstring>
#include<string>
#include<vector>
#include<map>
#include<set>
#include<queue>
using namespace std;
const int inf=1<<30;
int n,m,mp[3100][3100];
int use[3100];
int times=0;
struct dis
{
    int s,d;
    dis(int _s,int _d):s(_s),d(_d)
    {}
    bool operator <(const dis &b) const
    {
        if (d==b.d) return s>b.s;
        return d<b.d;
    }
};
int mincut(int &S,int &T)
{
    priority_queue<dis> q;
    queue<dis> p;
    dis t(0,0);
    for (int i=1;i<=n;i++)
        if (!use[i]) q.push(dis(i,0));
    while (!q.empty())
    {
        t=q.top();
        q.pop();
        if (T==t.s) return t.d;
        S=T;
        T=t.s;
        while (!q.empty())
        {
            times++;
            p.push(q.top());
            q.pop();
        }
        while (!p.empty())
        {
            times++;
            t=p.front();
            p.pop();
            q.push(dis(t.s,mp[T][t.s]+t.d));
        }
    }
    return q.top().d;
}
int main()
{
    while (~scanf("%d%d",&n,&m))
    {
        memset(mp,0,sizeof(mp));
        memset(use,0,sizeof(use));
        while (m--)
        {
            int u,v,w;
            scanf("%d%d%d",&u,&v,&w);
            mp[u][v]+=w;
            mp[v][u]+=w;
        }
        int ans=inf;
        int i,j;
        for (i=2;i<=n;i++)
        {
            int s=0,t=0;
            ans=min(ans,mincut(s,t));
            if (times>1e7) break;
            use[t]=true;
            for (j=1;j<=n;j++)
            {
                mp[s][j]+=mp[t][j];
                mp[j][s]+=mp[j][t];
            }
        }
        printf("%d\n",ans);
    }
    return 0;
}