#include <stdio.h>

#define IN "flux.in"
#define OUT "flux.out"
#define MAX 5005

FILE *fin=fopen(IN,"r");
FILE *fout=fopen(OUT,"w");

int n,m;
int f[MAX][MAX];
int v[MAX],p[MAX];
long flux;

void citire();
void alg();
void dfs(int);
void sat(int);

int main()
{
 citire();
  fclose(fin);
  
 alg();
 
 fprintf(fout,"%d",flux);
 fclose(fout);
 
 return 0;
}     

void citire()
{
 int i;
 int x,y,c;
     
 fscanf(fin,"%d %d ",&n,&m);
 for(i=1;i<=m;i++)
 {
  fscanf(fin,"%d %d %d ",&x,&y,&c);
  f[x][y]=c;
 }
}

void alg()
{
 p[1]=1;
 dfs(2);
}

void dfs(int k)
{
 int aux,i;

 if(p[k-1]==n)
  sat(k-1);
 else
  for(i=1;i<=n;i++)
   if(f[p[k-1]][i]!=0)
   {
    aux=f[p[k-1]][i];
    p[k]=i;
    v[k]=aux;

    dfs(k+1);
   }
}

void sat(int k)
{
 int i;
 int min=1000;

 for(i=2;i<=k;i++)
  if(v[i]<min)
   min=v[i];

 for(i=1;i<k;i++)
  f[p[i]][p[i+1]]-=min;

 for(i=2;i<=k;i++)
  v[i]-=min;

 flux+=min;
}