//100

#include <stdio.h>
#include <string.h>
#define MIN(a,b) ((a<b)?(a):(b))
#define CAP 32000
#define INF 1000000001
#define NMAX 64

int cost[NMAX][NMAX],a[NMAX][NMAX],c[NMAX][NMAX],f[NMAX][NMAX];
int mold[NMAX][NMAX],mnew[NMAX][NMAX];
int d[NMAX],p[NMAX];
int grin[NMAX],grout[NMAX];
int i,j,n,m,C;
int x,y,z;


void leg_sursa(int ind, int source, int cp, int cst)
{
    a[source][++a[source][0]] = ind;
    a[ind][++a[ind][0]] = source;
    c[source][ind] = cp;
    cost[source][ind] = cst;

}

void leg_nod(int n1, int n2, int cp, int cst)
{
   a[n1][++a[n1][0]] = n2;
   a[n2][++a[n2][0]] = n1;
   cost[n1][n2] = cst;
   cost[n2][n1] = -cst;
   c[n1][n2] = cp;
}

int belford()
{

   int ok,i,j,k;


   for (i = 0; i <= n+1; i++) { d[i] = INF; p[i] = -1; }

   p[0] = -1;
   d[0] = 0;
   ok = 1;

          for (k = 1; k <= n+1 && ok; k++)
              for (i = 0 , ok = 0; i <= n+1; i++)
                  for (j = 1; j <= a[i][0]; j++)
                  {
                      int t = a[i][j];

                      if (c[i][t] > f[i][t]  && d[t] > d[i] + cost[i][t])
                      {
                              d[t] = d[i] + cost[i][t];
                              p[t] = i;
                              ok = 1;
                      }
                  }

   return d[n+1] < INF;
}

void royf()
{

   int k, i, j;

	memcpy(mnew, cost, sizeof(cost));
     memcpy(mold, cost, sizeof(cost));

	for (k = 1; k <= n; k++)
	{
	      for (i = 1; i <= n; i++)
	       	for (j = 1; j <= n; j++)
	              if (mold[i][k] < INF && mold[k][j] < INF)
		            mnew[i][j] = MIN(mnew[i][j], mold[i][k] + mold[k][j]);

	      memcpy(mold, mnew, sizeof(mnew));
	}

          //memcpy(cost, mnew, sizeof(mnew));

}

void init()
{
  int i, j;

  for (i = 1; i <= n; i++)
      for (j = 1; j <= n; j++) cost[i][j] = INF * (i != j);
}

int main()
{

    freopen("traseu.in","r",stdin);
    freopen("traseu.out","w",stdout);

    scanf("%d %d",&n,&m);

    init();

    for (i = 1; i <= m; i++)
    {
         scanf("%d %d %d",&x,&y,&z);

         cost[x][y] = z;
         grin[y]++; grout[x]++;
         C += z;
    }

    royf();

    for (i = 1; i <= n; i++)
    {
          if (grin[i] > grout[i]) leg_sursa(i, 0, grin[i]-grout[i], 0);
          if (grin[i] < grout[i]) leg_sursa(n+1, i, grout[i]-grin[i], 0);
    }

    for (i = 1; i <= n; i++)
      for (j = 1;j <= n; j++)
          if ( grin[i] > grout[i] && grin[j] < grout[j] )
             leg_nod(i, j, CAP, mnew[i][j]);


    while ( 1 )
    {

          int minim = INF;

          if ( belford() )
          {

                    for (i = n+1; p[i] >= 0; i = p[i])
                    {
                        int cap = c[p[i]][i] - f[p[i]][i];

                        minim = MIN(minim, cap);
                    }

                    for (i = n+1; p[i] >= 0; i = p[i])
                    {
                        f[p[i]][i] += minim;
                        f[i][p[i]] -= minim;
                    }

                    C += minim * d[n+1];
          }
           else break;
    }

    printf("%d\n",C);

    fclose(stdin);
    fclose(stdout);

    return 0;
}