#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#define inf 2147000000
using namespace std;
ifstream f("traseu.in");
ofstream g("traseu.out");
vector <int> v[65];
queue <int> q;
int n,m,x,y,dmin[65],dp[65][65],gri[65],gre[65],c[65][65],cost[65][65],fol[65][65],use[65],ant[65],sol,s,t;

int BellmanFord()
{ int i,newc,nod,nod2;

   for(i=1;i<=n+2;i++)
    {dmin[i]=inf;
     ant[i]=0;
    }

    q.push(s); dmin[s]=0;

    while(!q.empty())
    { nod=q.front(); q.pop(); use[nod]=0;

       if (nod==t) continue;
        for(i=0;i<v[nod].size();i++)
        { nod2=v[nod][i]; newc=dmin[nod]+cost[nod][nod2];
           if (fol[nod][nod2]<c[nod][nod2] && cost[nod][nod2]!=inf && newc<dmin[nod2])
           { dmin[nod2]=newc;
             ant[nod2]=nod;
             if (!use[nod2]) {use[nod2]=1; q.push(nod2);}
           }
        }
    }

 return (dmin[t]!=inf);
}
int main()
{ int i,j,k,res;
    f>>n>>m;

     for(i=1;i<=m;i++)
     { f>>x>>y;
       f>>dp[x][y];
       sol+=dp[x][y];
       gre[x]++;
       gri[y]++;
     }

   for(i=1;i<=n;i++)
    for(j=1;j<=n;j++)
     if (!dp[i][j]) dp[i][j]=inf;

  for(k=1;k<=n;k++)
   for(i=1;i<=n;i++)
    for(j=1;j<=n;j++)
     if (i!=j && dp[i][k]!=inf && dp[k][j]!=inf && dp[i][k]+dp[k][j]<dp[i][j])
      dp[i][j]=dp[i][k]+dp[k][j];

  s=n+1; t=n+2;

   for(i=1;i<=n;i++)
   {
      if (gri[i]>gre[i])
      { v[s].push_back(i);
        c[s][i]=gri[i]-gre[i];

      }

      if (gre[i]>gri[i])
      { v[i].push_back(t);
        c[i][t]=gre[i]-gri[i];

      }
   }

    for(i=1;i<=n;i++)
     for(j=1;j<=n;j++)
      if (i!=j && gri[i]>gre[i] && gre[j]>gri[j])
       {   v[i].push_back(j);
           v[j].push_back(i);
           c[i][j]=inf;
           cost[i][j]=dp[i][j];
           cost[j][i]=-dp[i][j];
       }

 BellmanFord();

    while(BellmanFord())
    {
       x=t; res=inf;

       while(ant[x])
       { res=min(res,c[ant[x]][x]-fol[ant[x]][x]);
         x=ant[x];
       }

        x=t; sol+=dmin[t]*res;

       while(ant[x])
       { fol[ant[x]][x]+=res;
         fol[x][ant[x]]-=res;
         x=ant[x];
       }
    }

 g<<sol<<"\n";

    return 0;
}