#include <stdio.h>
#include <queue>
#include <bitset>
#define INF 1000000000
#define N 128
using namespace std;
int n,m,S,D,i,j,k,x,y,z,costflux,minim,aux;
int g[N],gi[N],ge[N],d[N],path[N],t[N],pus[N];
int cap[N][N],cst[N][N],a[N][N];
int v[N][N];

void bellman(){
 queue<int>Q; bitset<N>iq; int nod,fiu;
 for (i=0;i<=D;++i)d[i]=INF;
 d[S]=0;
 Q.push(S);iq[S]=1;
 while (!Q.empty()){
    nod=Q.front(); Q.pop();
    iq[nod]=0;
    for (i=0;i<g[nod];++i){
      fiu=v[nod][i];
      if (cap[nod][fiu])
        if (d[nod]+cst[nod][fiu] < d[fiu]){
          d[fiu]=d[nod]+cst[nod][fiu];
          t[fiu]=nod;
          if (!iq[fiu]){ Q.push(fiu); iq[fiu]=1; }
       }
    }
 }
}
int main(){
  freopen("traseu.in","r",stdin); freopen("traseu.out","w",stdout);
  scanf("%d %d",&n,&m);
  for (i=1;i<=m;++i){
    scanf("%d %d %d",&x,&y,&z);
    a[x][y]=z;
    ge[x]++; gi[y]++;
    costflux+=z;
  }
  //aflare drumuri minime in graf
	for (k=1;k<=n;++k)
    for (i=1;i<=n;++i)
      for (j=1;j<=n;++j)
        if (i!=j)
          if (a[i][k] && a[k][j])
            if (a[i][k]+a[k][j]<a[i][j] || !a[i][j])a[i][j]=a[i][k]+a[k][j];
  //contruire graf flux
  
  S=0;D=n+1;
  for (i=1;i<=n;++i)
    if (gi[i]>ge[i]){v[S][g[S]++]=i;v[i][g[i]++]=S;cap[S][i]=gi[i]-ge[i];pus[i]=1;}
    else if (gi[i]<ge[i]){v[D][g[D]++]=i;v[i][g[i]++]=D;cap[i][D]=ge[i]-gi[i];pus[i]=2;}
  
    for (i=1;i<=n;++i)
    for (j=1;j<=n;++j)
      if (a[i][j])
       if (pus[i]==1 && pus[j]==2){
        v[i][g[i]++]=j;v[j][g[j]++]=i;
        cap[i][j]=INF; cst[i][j]=a[i][j]; cst[j][i]=-a[i][j];
      }
  
  //// calulare flux cost minim
 do{
	 bellman();
	 if (d[D]==INF)break;
	 m=0;aux=D;
	 while (aux!=0){path[++m]=aux;aux=t[aux];}
	 path[++m]=0;
	 minim=INF;
	 for (i=1;i<m;++i)
			if (cap[path[i+1]][path[i]]<minim) minim=cap[path[i+1]][path[i]];
	 for (i=1;i<m;++i){
			cap[path[i+1]][path[i]]-=minim;
			cap[path[i]][path[i+1]]+=minim;
	 }
	 costflux+=minim*d[D];
 }while(1);
 printf("%ld\n",costflux);
return 0;
}



/*
 void build(){  
#      int i,j,ns,nd;  
#      for (i=1,ns=0;i<=n;++i)  
#       if  (dint[i]>dext[i]) v[++ns]=i;  
#      for (i=1,nd=ns;i<=n;++i)  
#       if (dint[i]<dext[i]) v[++nd]=i;  
#      source=0;sink=nd+1;  
#      for (i=1;i<=ns;++i){  
#       r[source][i]=dint[v[i]]-dext[v[i]];  
#       c[source][i]=0;}  
#      for (i=ns+1;i<=nd;++i){  
#       r[i][sink]=dext[v[i]]-dint[v[i]];  
#       c[i][sink]=0;}  
#      for (i=1;i<=ns;++i)  
#       for (j=ns+1;j<=nd;++j){  
#        r[i][j]=Inf;  
#        c[i][j]=a[v[i]][v[j]];  
#        c[j][i]=-c[i][j];}  
#      }  

a[i][j]= dist min intre nodurile i si j in graful initial.
r[i][j]= fluxul
c[i][j]= costul
*/