#include <fstream>
#define Inf 32000
using namespace std;
 ifstream in("traseu.in");
 ofstream out("traseu.out");
 int n,m,i,j,k,c[70][70],x,y,cost,g_intrare[70]={0},g_iesire[70]={0},d[70],sum=0,nod,suminit=0,pos=0;
 void init()
 {in>>n>>m;
  for(i=0;i<=n+1;i++)
   for(j=i+1;j<=n+1;j++)
    c[i][j]=c[i][j]=Inf;
   for(i=1;i<=m;i++)
    {in>>x>>y>>cost;c[x][y]=cost;g_intrare[y]++;g_iesire[x]++;suminit+=cost;}
   for(i=1;i<=n;i++)
    {if(g_intrare[i]>g_iesire[i]) {c[0][i]=0; g_iesire[0]++;}
     else if(g_intrare[i]<g_iesire[i]) {c[i][n+1]=0;g_intrare[n+1]++;}}
  for(i=0;i<=n+1;i++)
   d[i]=c[0][i];
}
void bellman_ford()
{ int suma;
for(i=0;i<=n+1;i++)
 for(j=0;j<=n+1;j++)
  for(k=0;k<=n+1;k++)
   if(c[j][k]!=Inf && d[k]>d[j]+c[j][k]){d[k]=d[j]+c[j][k];if(j==0) nod=k;}
 c[0][k]=suminit;pos++;

}

int main()
{  suminit=0;init();  sum=suminit;
while(pos<=g_iesire[0])
{d[n+1]=Inf;
bellman_ford();
 sum+=d[n+1]; }
   out<<sum;
      return 0;
}