//program 3.4 Flux maxim
#include <fstream>
#include <iostream>
#include <queue>
using namespace std;
int a[1001][1001], c[1001][1001], f[1001][1001];
int viz[1001],T[1001];
int n,m,lung,minim;
ifstream fin("maxflow.in");
ofstream fout("maxflow.out");
struct arc{int n1,n2;};
arc drum[101];
int bf()
{
 int i,j;
 queue <int> q;
 fill(viz,viz+101,0);fill(T,T+101,0);
 q.push(1);
 viz[1] = 1;
 while (q.empty() != 1)
 { i = q.front();
 if (i == n)
 return 1;
 q.pop();
 for (j = 1;j<=n;j++)
 { if (viz[j] == 0 && c[i][j] - f[i][j] > 0)
 {//arc parcurs in sens direct
 viz[j] = 1;
 T[j] = i;
 q.push(j);
 }
 if (viz[j] == 0 && f[j][i] > 0)
 {//arc parcurs in sens invers
 viz[j] = 1;
 T[j] = i;
 q.push(j);
 }
 }
 }
 return 0;
}
void calcdrum()
{
 int i=0,b=n,a;
 minim = 10000000;
 a = T[b];
 while (a!=0)
 {
 drum[i].n1 = a;
 drum[i].n2 = b;
 if (c[a][b] > f[a][b])
 {if (minim > c[a][b] - f[a][b])
 minim = c[a][b] - f[a][b];
 }
 else
 if (minim > f[b][a])
 minim = f[b][a];
 i++;
 b = a;
 a = T[b];
 }
 lung = i;
}
int main()
{
 int i,j,k,ok=1;
 fin >> n >> m;
 for (i=0;i<m;i++)
 {fin >> i >> j;
 fin >> c[i][j];
 }
 while (ok == 1)
 {
 ok=bf(); //returneaza 1 daca gaseste un drum
 if (ok == 1)
 { calcdrum(); //calculeaza si minimul
/*
 cout<<"\n\ngasit un drum de lungime "<< lung;
 cout<<" capacitate reziduala "<< minim << endl;
 cout << "format din arcele: ";
*/
 for (k=0;k<lung;k++)
 { i = drum[k].n1;
 j = drum[k].n2;
// cout<< i << '-' << j << " , ";
 if (c[i][j] - f[i][j] > 0)
 f[i][j] += minim;
 else
 f[j][i] -= minim;
 }
 }
 }

 int fluxmax = 0;
 for (i=1;i<=n;i++)
 fluxmax += f[1][i];
// cout<<"\n\nflux maxim= "
    fout<<fluxmax<<endl;
/*
 cout<<"starea fiecarui arc:capacitate/flux\n";
 for (i=1;i<=n;i++)
 for (j=1;j<=n;j++)
 if (c[i][j]>0)
 { cout<<'('<<i<<'-'<<j<<"):";
 cout<<c[i][j]<<'/'<<f[i][j]<<endl;
 }
*/
 return 0;
}