//nrA[C(x,?)] = max(din[x] - dout[x],0);
//nrA[C(?,y)] = dout[y]-dinforward[y]-dinback[y]-dincross[y] = max(dout[y]-din[y],0);

#include <fstream.h>

#define MAXN 70

int n,m;

int delta;
int cost[MAXN][MAXN];
int gr[MAXN];

int cap[MAXN][MAXN];
int f[MAXN][MAXN];

int cst[MAXN];

int totalcost;

int K;
int path[MAXN];

int pathcap;

int prec[MAXN];
int is[MAXN];

int st=0,ed=0;
int stack[MAXN];

void QADD(int i)
{
 if(is[i]) return;
 if(st==ed) stack[-1]=1; //Signal overflow
 stack[ed++]=i;
 if(ed>=MAXN) ed=0;
}

int QPop()
{
 if(st==ed) return -1;

 int r = stack[st++];
 if(st>=MAXN) st=0;
 return r;
}

int FindPath()
{
 int i,j;
 K = 0;
 prec[n+1]=-1;
 for(i=0;i<=n+1;i++) prec[i]=-1;
 st=0; ed=0;
 QADD(0);
 while(1)
  {
   i=QPop();
   if(i==-1)
    break;
   for(j=1;j<=n+1;j++)
    if(cap[i][j]-f[i][j]>0)
     if(cst[j]==0 || cst[j]>cst[i]+cost[i][j]-cost[j][i])
       {
	cst[j] = cst[i]+cost[i][j]-cost[j][i];
	prec[j] = i;
	QADD(j);
       }
  }
 i=n+1;
 if(prec[i]==-1) 
  return 0;
 while(1)
 {
  path[K++]=i;
  i = prec[i];
  if(i==-1) break;
  if(K>=MAXN) path[-1]=1; //Signal neg. cycle or disconnected graph
 }

 for(i=0;i<K/2;i++) {int tmp = path[i];path[i]=path[K-1-i];path[K-1-i]=tmp;}
 pathcap = cap[path[0]][path[1]] - f[path[0]][path[1]];
 for(i=2;i<K;i++)
  if(cap[path[i-1]][path[i]] - f[path[i-1]][path[i]] < pathcap)
    pathcap = cap[path[i-1]][path[i]] - f[path[i-1]][path[i]];

 return 1;
}

void FillPath()
{
 int i;
 for(i=1;i<K;i++)
  {
   f[path[i-1]][path[i]]+=pathcap;
   f[path[i]][path[i-1]]-=pathcap;
   totalcost += cost[path[i-1]][path[i]]*pathcap - cost[path[i]][path[i-1]]*pathcap;
  }
}

ifstream in("traseu.in");
ofstream out("traseu.out");

int main()
{
 in>>n>>m;
 int i,j,a,b,c;
 for(i=0;i<m;i++)
 {
   in>>a>>b>>c;
   cost[a][b]=c;
   delta+=c;
   gr[a]--;gr[b]++;
 }
 int k;
 for(k=1;k<=n;k++)
  for(i=1;i<=n;i++) if(i!=k)
   for(j=1;j<=n;j++) if(j!=i)
    if(cost[i][j]>cost[i][k]+cost[k][j] || cost[i][j]==0)
      cost[i][j]=cost[i][k]+cost[k][j];

 for(i=1;i<=n;i++)
  {
   if(gr[i]>0)
    {
     cap[0][i]=gr[i];
     for(j=1;j<=n;j++)
      if(gr[j]<0)
	{cap[i][j]=MAXN;cost[j][i]=0;}
    }
   if(gr[i]<0)
    {
     cap[i][n+1]=-gr[i];
    }
  }

 totalcost = 0;
 while(FindPath()>0)
  {
   FillPath();
  }
 totalcost+=delta;
 out<<totalcost<<"\n";
 return 0;
}