#include <stdio.h>
#include <string.h>
#include <vector>
using namespace std;
#define FI fopen("maxflow.in","r")
#define FO fopen("maxflow.out","w")

long long sol;
long mat[1001][1001];
int n;
vector<int> nod[1001];

void citeste(FILE *f) {
  int i,m,a,b;
  long c;
  fscanf(f,"%i%i",&n,&m);
  for(i=0;i<m;i++) {
    fscanf(f,"%i%i%li",&a,&b,&c);
    if(a==1 && b==n) {
      sol+=c;
      continue;
    }
    mat[a][b]=c;
    nod[a].push_back(b);
    nod[b].push_back(a);
  }
}

int createArbore(int par[],int sf[],int &sfLen) {
  int i,j,k,lim,st[1001];
  char viz[1001];
  for(i=2;i<n;i++)
    viz[i]=0;
  st[0]=1;
  viz[1]=1;
  i=0;
  j=1;
  sfLen=0;
  while(i<j) {
    lim=nod[st[i]].size();
    for(k=0;k<lim;k++)
      if(viz[nod[st[i]][k]]==0 && mat[st[i]][nod[st[i]][k]]) {
	if(nod[st[i]][k]==n) {
	  sf[sfLen]=st[i];
	  sfLen++;
	}
	else {
	  par[nod[st[i]][k]]=st[i];
	  viz[nod[st[i]][k]]=1;
	  st[j]=nod[st[i]][k];
	  j++;
	}
      }
    i++;
  }
  return sfLen;
}

long long min(long long a,long long b) { if(a<b) return a; return b; }
long parcurge(int par[],int nodAct,int nodAnt,long long max) {
  if(nodAct == 1) {
    max=min(max,mat[nodAct][nodAnt]);
    mat[nodAct][nodAnt]-=max;
    mat[nodAnt][nodAct]+=max;
    return max;
  }
  max=parcurge(par,par[nodAct],nodAct,min(mat[nodAct][nodAnt],max));
  mat[nodAct][nodAnt]-=max;
  mat[nodAnt][nodAct]+=max;
  return max;
}

void flux() {
  int i,par[1001],sf[1000],sfLen;
  while(createArbore(par,sf,sfLen))
    for(i=0;i<sfLen;i++)
      sol+=parcurge(par,sf[i],n,0x7fffffffffffffffll);
}

int main() {
  citeste(FI);
  flux();
  fprintf(FO,"%lli",sol);
  return 0;
}