#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <set>
#include <queue>
#include <deque>

using namespace std;

ifstream f("maxflow.in");
ofstream g("maxflow.out");

#define nmax 1005
#define ll long long

int n, m, capac[nmax][nmax], flux[nmax][nmax], t[nmax];
bool viz[nmax];
vector<int> gf[nmax];
queue<int> q;

void citeste(){
    f >> n >> m;
    int x, y, c;
    for(int i=1; i<=m; ++i){
        f >> x >> y >> c;
        gf[x].push_back(y);
        gf[y].push_back(x);
        capac[x][y] = c;
    }
}

int bfs(){
    for(int i=0; i<=n; ++i) viz[i] = 0, t[i] = 0;
    for(;q.size(); q.pop());

    q.push(1); viz[1] = 1;
    for(; q.size(); ){
        int nod = q.front(); q.pop();
        for(int i=0; i<gf[nod].size(); ++i){
            int vc = gf[nod][i];
            if (viz[vc] == 1) continue;// daca a fost deja vizitat
            if (capac[nod][vc] == flux[nod][vc]) continue;//daca numai pot pompa flux(sau cazul initial nu exista flux dar nu e nici capac
                                                                                      // pt ca e muchie de intoarcere)
            t[vc] = nod;
            viz[vc] = 1; q.push(vc);
            if (vc == n) return 1;
        }
    }

    return 0;// inseamna ca nu am ajuns in n;
}

void rezolva(){
     // in primul rand e orientat deci pe muchiile care nu exista initial capac e nula; fluxul e nul peste tot
     // acum bag un flux pe primul drum pe care mi-l gaseste bf-ul; prin faptul ca drumul gasit de bf
     // nu va fi tot timup optim o sa trebuiasca sa scad fluxul pe muchia inversa;
     int Max = 0;
     for(; bfs()!=0;){
        //aleg fluxul pe care o sa il bag pe drumul asta
        int Min = (1<<29);// tot timpul fluxul va fi strict pozitiv
        for(int i=n; t[i] != 0; i=t[i]){
            // m-am dus pe muchia t[i] -> i;
            Min = min(Min, capac[ t[i] ][i] - flux[ t[i] ][i]);// o sa bag cat imi mai ramane
        }

        for(int i=n; t[i] != 0; i=t[i]){
            // m-am dus pe muchia t[i] -> i;
            flux[ t[i] ][i] += Min;
            flux[i][ t[i] ] -= Min;// pe muchia inversa il scad pentru a nu bloca conducta asta
        }

        Max += Min;// cresc fluxul total
     }

     cout << Max << "\n";
     g << Max << "\n";
}

int main(){
    citeste();
    rezolva();

    f.close();
    g.close();

    return 0;
}