#include<stdio.h>
#define inf 0x3f3f3f3f
long int dr[62][62],a[62][62],f[62][62],gi[62],go[62],c[62][62],cd[10000],d[62],i,j,n,m,k,l,p,ss,min,t[62],s[62];
FILE *in,*out;

void intoarce(int v){
int i=n+1;int l;
while(i!=0)
 f[(l=t[i])][i]+=v,f[i][l]-=v,i=l;
}

long int drmin(){
int i,j,p,u,min,l;
for(i=0;i<=n+1;i++)
 d[i]=inf,gi[i]=inf;
d[0]=0;p=u=1;cd[1]=0,gi[0]=inf;
while(p<=u){
 i=cd[p++];
  for(j=1;j<=n+1;j++)
    if(i!=n+1&&c[i][j]>f[i][j]&&d[j]>d[i]+dr[i][j]){
     d[j]=d[i]+dr[i][j],t[j]=i,cd[++u]=j;
      if(gi[i]<(l=c[i][j]-f[i][j]))
       gi[j]=gi[i];
      else
       gi[j]=l;
    }
}
if(d[n+1]==inf)
 return 0;
intoarce(gi[n+1]);
return(d[n+1]*gi[n+1]);
}

int main(){
in=fopen("traseu.in","rt");
out=fopen("traseu.out","wt");
fscanf(in,"%ld%ld",&n,&m);
for(i=0;i<=n+1;i++)
  for(j=0;j<=n+1;j++)
   a[i][j]=inf,c[i][j]=-43232,dr[i][j]=inf,f[i][j]=0;
for(i=1;i<=m;i++){
 fscanf(in,"%ld%ld%ld",&k,&l,&p);
 gi[l]++;go[k]++;a[k][l]=p;ss+=p;
}
for(i=1;i<=n;i++){
  for(j=1;j<=n;j++)
   d[j]=inf,s[j]=0;
 d[i]=0;
  for(j=1;j<=n;j++){
   min=inf;
    for(k=1;k<=n;k++)
      if(!s[k]&&min>d[k])
       min=d[k],p=k;
   s[p]=1;
    for(k=1;k<=n;k++)
      if(!s[k]&&d[k]>(l=d[p]+a[p][k]))
       d[k]=l;
  }
  for(j=1;j<=n;j++)
   dr[i][j]=d[j];
}
for(i=1;i<=n;i++)
  for(j=1;j<=n;j++){
    if(gi[j]<go[j])
     dr[j][n+1]=0,c[j][n+1]=go[j]-gi[j],c[n+1][j]=0;
    else
     dr[j][n+1]=inf;
    if(gi[i]>go[i]){
     dr[0][i]=0,c[0][i]=gi[i]-go[i],c[i][0]=0;
      if(gi[j]<go[j])
       c[i][j]=inf,c[j][i]=0,dr[j][i]=-dr[i][j];
      else
       dr[i][j]=inf;
    }
    else
     dr[0][i]=inf;
  }
while(l=drmin())
 ss+=l;
fprintf(out,"%ld",ss);
return 0;
}