#include <cstdio>
#include <queue>
#include <algorithm>

using namespace std;

const int inf=1e9;

queue<int> q;
int n,d[70],cost[70][70],cap_flow[70][70],vaz[70],tata[70],grad[70];
vector<int> v[70];

int Bellman_ford()
{
    for(int i=0;i<=n;i++) d[i]=inf,vaz[i]=0;
    d[0]=0;vaz[0]=1;
    q.push(0);
    while(!q.empty())
    {
        int nod=q.front();
        vaz[nod]=0;
        q.pop();
        for(int i=0;i<v[nod].size();i++)
        {
            int vec=v[nod][i];
            if(cap_flow[nod][vec]>0 && d[nod]+cost[nod][vec]<d[vec])
            {
                d[vec]=d[nod]+cost[nod][vec];
                tata[vec]=nod;
                if(vec!=n && vaz[vec]==0) {vaz[vec]=1;q.push(vec);}
            }
        }
    }
    return d[n]<inf;
}

int main()
{
    freopen("traseu.in","r",stdin);
    freopen("traseu.out","w",stdout);
    int sol=0,x,y,c,m;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++)
    {
        scanf("%d%d%d",&x,&y,&c);
        sol+=c;
        v[x].push_back(y);
        v[y].push_back(x);
        cost[x][y]=c;
        cost[y][x]=-c;
        cap_flow[x][y]=inf;
        grad[x]--;grad[y]++;
    }
    for(int i=1;i<=n;i++)
        if(grad[i]>0)
        {
            v[0].push_back(i);
            v[i].push_back(0);
            cap_flow[0][i]=grad[i];
        }
        else if(grad[i]<0)
        {
            v[i].push_back(n+1);
            v[n+1].push_back(i);
            cap_flow[i][n+1]=-grad[i];
        }
    n++;
    while(Bellman_ford())
    {
        for(int i=0;i<v[n].size();i++)
        {
            int vec=v[n][i];
            if(cap_flow[vec][n]>0 && d[vec]<inf)
            {
                int s=1e9;
                for(int nod=n;nod!=0;nod=tata[nod]) s=min(s,cap_flow[tata[nod]][nod]);
                for(int nod=n;nod!=0;nod=tata[nod])
                {
                    cap_flow[tata[nod]][nod]-=s;
                    cap_flow[nod][tata[nod]]+=s;
                    sol+=s*cost[tata[nod]][nod];
                }
            }
        }
    }
    printf("%d",sol);
    return 0;
}