#include<cstdio>
#include<vector>
#include<cstring>
#include<utility>
#include<ctime>
#include<cstdlib>
using namespace std;
vector<pair<int,int> > g[3001];
int main()
{
    srand((unsigned)time(NULL));
    int n,m,u,v,w,i,j,ans,anst,times,cost[3001],lsize,rsize;
    bool tag[3001],rep;
    while(~scanf("%d%d",&n,&m))
    {
        for(i=1;i<=n;++i)
        {
            g[i].clear();
        }
        while(m--)
        {
            scanf("%d%d%d",&u,&v,&w);
            if(u==v)
            {
                continue;
            }
            g[u].push_back(make_pair(v,w));
            g[v].push_back(make_pair(u,w));
        }
        
        ans=1e8;
        times=0;
        do
        {
            ++times;
            memset(tag+1,false,sizeof(bool)*n);
            tag[times]=true;
            lsize=1;
            rsize=n-1;
            anst=0;
            memset(cost+1,0,sizeof(int)*n);
            for(i=1;i<=n;++i)
            {
                for(j=0;j<g[i].size();++j)
                {
                    v=g[i][j].first;
                    w=g[i][j].second;
                    if(tag[i]!=tag[v])
                    {
                        anst+=w;
                        cost[i]-=w;
                        cost[v]-=w;
                    }
                    else
                    {
                        cost[i]+=w;
                        cost[v]+=w;
                    }
                }
            }
            anst>>=1;
            for(i=1;i<=n;++i)
            {
                cost[i]>>=1;
            }
            rep=true;
            while(rep)
            {
                rep=false;
                for(i=2;i<=n;++i)
                {
                    if(cost[i]<0 && ((!tag[i]) || lsize>1) && ((tag[i]) || rsize>1))
                    {
                        rep=true;
                        anst+=cost[i];
                        if(tag[i])
                        {
                            --lsize;
                            ++rsize;
                        }
                        else
                        {
                            ++lsize;
                            --rsize;
                        }
                        for(j=0;j<g[i].size();++j)
                        {
                            v=g[i][j].first;
                            w=g[i][j].second<<1;
                            if(tag[i]!=tag[v])
                            {
                                cost[i]+=w;
                                cost[v]+=w;
                            }
                            else
                            {
                                cost[i]-=w;
                                cost[v]-=w;
                            }
                        }
                        tag[i]=!tag[i];
                    }
                }
            }
            ans=min(ans,anst);
        }while(times<n);
        printf("%d\n",ans);
    }
    return 0;
}