#include<stdio.h>
#include<algorithm>
#include<cstring>
#include<vector>
#include<queue>
#define pb push_back
#define maxn 70
#define inf 0x3f3f3f3f
using namespace std;

int n,m,sol,S,D;
int used[maxn],father[maxn],d[maxn],in[maxn],out[maxn];
int c[maxn][maxn],Cost[maxn][maxn],f[maxn][maxn];
vector<int> l[maxn];

void read()
{
    int x,y,cst;
    scanf("%d%d",&n,&m);

    for(int i=1;i<=n;i++)
     for(int j=1;j<=n;j++)
      Cost[i][j]=inf;

    for(int i=1;i<=m;i++)
    {
        scanf("%d%d%d",&x,&y,&cst); sol+=cst;
        Cost[x][y]=cst; in[y]++; out[x]++;
    }
}

void roy()
{
    for(int k=1;k<=n;k++)
     for(int i=1;i<=n;i++)
      for(int j=1;j<=n;j++)
       if(Cost[i][k]+Cost[k][j]<Cost[i][j])
        Cost[i][j]=Cost[i][k]+Cost[k][j];
}

void build_network()
{
    S=0; D=n+1;
    for(int i=1;i<=n;i++)
    if(in[i]>out[i])
     {
         c[S][i]=in[i]-out[i]; Cost[S][i]=Cost[i][S]=0;
         l[S].pb(i); l[i].pb(S);
     }
     else
      if(in[i]<out[i])
      {
          c[i][D]=out[i]-in[i]; Cost[i][D]=Cost[D][i]=0;
          l[i].pb(D); l[D].pb(i);
      }
    for(int i=1;i<=n;i++) if(in[i]>out[i])
     for(int j=1;j<=n;j++) if(in[j]<out[j])
     {
         c[i][j]=inf; Cost[j][i]=-Cost[i][j];
         l[i].pb(j); l[j].pb(i);
     }
}

int bellman()
{
    int k;
    queue<int> q;

   for(int i=S;i<=D;i++) d[i]=inf,used[i]=0;
    d[S]=0;
    for(q.push(S),used[S]=1;!q.empty();q.pop(),used[k]=0)
    {
        k=q.front();
        for(unsigned int i=0;i<l[k].size();i++)
         if(f[k][l[k][i]]<c[k][l[k][i]] && d[k]+Cost[k][l[k][i]]<d[l[k][i]])
         {
             d[l[k][i]]=d[k]+Cost[k][l[k][i]];
             father[l[k][i]]=k;
             if(!used[l[k][i]])
             {
                 q.push(l[k][i]);
                 used[l[k][i]]=1;
             }
         }
    }
    if(d[D]==inf) return 0;
    return 1;
}

void fmcm()
{
    int Min=inf;
    for(;bellman();)
    {
        Min=inf;
        for(int i=D;i!=S;i=father[i])
         Min=min(Min,c[father[i]][i]-f[father[i]][i]);
        for(int i=D;i!=S;i=father[i])
        {
            f[father[i]][i]+=Min;
            f[i][father[i]]-=Min;
        }
        sol+=Min*d[D];
    }
}

int main()
{
    freopen("traseu.in","r",stdin);
    freopen("traseu.out","w",stdout);

    read();
    roy();
    build_network();
    fmcm();
    printf("%d",sol);

    fclose(stdin);
    fclose(stdout);
    return 0;
}