#include <stdio.h>
#include <string>

#define maxn 70
#define maxx 3710
#define inf 10000
#define maxv 1000000000

int g[maxn],in[maxn],out[maxn];
int x[maxx],y[maxx],z[maxx],a[maxx];
int f[maxn][maxn],cap[maxn][maxn],d[maxn][maxn],cost[maxn][maxn];
int n,m,sol,sum;
int found,from[maxn],c[maxn];

void RoyFloyd()
{
     int i,j,k;
     
     for (k=1;k<=n;k++)
       for (i=1;i<=n;i++) 
         if (i!=k)
           for (j=1;j<=n;j++)
             if ((i!=j) && (j!=k) && (d[i][k]+d[k][j]<d[i][j])) d[i][j]=d[i][k]+d[k][j];
}

int BellmanFord(int S,int D)
{
    int i,j,stop=0,min=maxv;
    
    for (i=0;i<=n+1;i++) c[i]=maxv;
	c[S]=0;
    
    while (!stop)
    {
          stop=1;
          
          for (i=0;i<=n+1;i++)
            for (j=g[i];j<g[i+1];j++)
              if ((cap[i][a[j]]-f[i][a[j]]>0) && (c[i]+cost[i][a[j]]<c[a[j]]))
              {
                   from[a[j]]=i;
                   c[a[j]]=c[i]+cost[i][a[j]];
                   stop=0;
              }
    }
    
    if (c[D]!=maxv)
    {
         found=1;
         
         i=D;
         while (i!=S)
         {
               if (cap[from[i]][i]-f[from[i]][i]<min) min=cap[from[i]][i]-f[from[i]][i];
               i=from[i];
         } 
         
         i=D;         
         while (i!=S)
         {
               f[from[i]][i]+=min;
               f[i][from[i]]-=min;
               i=from[i];
         }
         
         return c[D]*min;
    }
    
    return 0;
}

int Flux()
{
    int rez=0;
    found=1;
    
    while (found)
    {
          found=0;
          rez+=BellmanFord(0,n+1);
    }
    
    return rez;
}

int main()
{
    freopen("traseu.in","r",stdin);
    freopen("traseu.out","w",stdout);
    
    scanf("%d %d",&n,&m);
    
    int i,j,aux;
    
    for (i=1;i<=n;i++)
      for (j=1;j<=n;j++) 
        if (i!=j) d[i][j]=maxv;
    
	for (i=1;i<=m;i++)
	{
		scanf("%d %d %d",&x[i],&y[i],&z[i]);
		g[x[i]]++;
		g[y[i]]++;
		in[x[i]]++;
		out[y[i]]++;
		cap[x[i]][y[i]]=inf;
		cost[x[i]][y[i]]=z[i];
		cost[y[i]][x[i]]=-z[i];
		d[x[i]][y[i]]=z[i];
		sum+=z[i];
	}

	for (i=1;i<=n;i++)
	  if (out[i]>in[i])
	  {
			g[0]++;
			g[i]++;
			cap[0][i]=out[i]-in[i];
			m++;
			x[m]=0;
			y[m]=i;
	  }

	for (i=1;i<=n;i++)
	  if (out[i]<in[i])
	  {
			g[i]++;
			g[n+1]++;
			cap[i][n+1]=in[i]-out[i];
			m++;
			x[m]=i;
			y[m]=n+1;
	  }

	for (i=1;i<=n+2;i++) g[i]+=g[i-1];

	for (i=1;i<=m;i++)
	{
		a[g[x[i]]--]=y[i];
		a[g[y[i]]--]=x[i];
	}

	for (i=0;i<=n+2;i++) g[i]++;

/*	RoyFloyd();
	sol=maxv;*/
	
	sol=Flux();

/*	for (i=1;i<=n;i++)  //atentie
	{
        for (j=1;j<=n;j++)
		  if (in[j]<out[j]) cost[0][j]=d[i][j];

		for (j=1;j<=n;j++)
		  if (out[j]<in[j]) cost[j][n+1]=d[j][i];

        memset(f,0,sizeof(f));

		aux=Flux();
        if (aux<sol) sol=aux;
    }*/
    
    sol+=sum;
    
    printf("%d\n",sol);
        
    return 0;
}