//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[1001];
int bf(int start,int fin)
{
 int i,j;
 queue <int> q;
 fill(viz,viz+1001,0);fill(T,T+1001,0);
 q.push(start);
 viz[start] = 1;
 while (q.empty() != 1)
 { i = q.front();
 if (i == fin)
 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(1,n); //returneaza 1 daca gaseste un drum
    if (ok == 1){
        calcdrum(); //calculeaza si minimul
        for (k=0;k<lung;k++){
            i = drum[k].n1;
            j = drum[k].n2;
            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];
 fout<<fluxmax<<endl;
 return 0;}