#include <stdio.h>
#include <queue>
#include <bitset>
#define INF 1000000000
#define N 64
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];
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=1;i<=N;++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 (i=1;i<=n;++i)
    for (j=1;j<=n;++j)
      if (i!=j)
        for (k=1;k<=n;++k)
          if (i!=k && j!=k)
            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];}
    else if (gi[i]<ge[i]){v[D][g[D]++]=i;v[i][g[i]++]=D;cap[i][D]=ge[i]-gi[i];}
  
    for (i=1;i<=n;++i)
    for (j=1;j<=n;++j)
      if (a[i][j]){
        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];}
	 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;
}