#include <bits/stdc++.h>
using namespace std;

void Citire(vector<vector<pair<int,int>>> &lisAdiacenta)
{
    ifstream fin("maxflow.in");
    vector<pair<int,int>>aux(1,{-1, -1});

    int N, M;
    fin >> N >> M;
    lisAdiacenta.resize(N+1, aux);

    for(int i = 1; i <= M; ++i){
        int x, y, c;
        fin >> x >> y >> c;
        lisAdiacenta[x].push_back({y,c});
    }
}

bool BFS_EK(vector<vector<int>> rezidual, int S, int T, vector<int> &tati)
{
    vector<bool> viz(rezidual.size(), 0);
    queue<int> coada;

    coada.push(S);
    viz[S] = 1;
    tati.resize(rezidual.size(), -1);

    while(!coada.empty()) {
        int x = coada.front();
        coada.pop();

        for(int i = 1; i < rezidual[x].size(); ++i) {
            if(!viz[i] && rezidual[x][i] > 0) {
                if(i == T) {
                    tati[i] = x;
                     return true;
                }
                coada.push(i);
                tati[i] = x;
                viz[i] = 1;
            }
        }
    }
    return false;
}



int ElmondsKarp(vector<vector<pair<int,int>>> lisAdiacenta, int S, int T, const int capacitateMax)
{

    vector<vector<int>> rezidual(lisAdiacenta.size(), vector<int>(lisAdiacenta.size(), 0));
    for(int i = 1; i < lisAdiacenta.size(); ++i){
        for(int j = 1; j < lisAdiacenta[i].size(); ++j) {
            rezidual[i][lisAdiacenta[i][j].first] = lisAdiacenta[i][j].second;
        }
    }

    vector<int> tati(lisAdiacenta.size(), -1);
    int fluxMaxim = 0;

    while(BFS_EK(rezidual, S, T, tati)) {
        int x;
        int fluxDrum  = capacitateMax;
        for(int i = T; i != S; i = tati[i]) {
            x = tati[i];
            fluxDrum = min(fluxDrum, rezidual[x][i]);
        }
        for(int i = T; i != S;i = tati[i]) {
            x = tati[i];
            rezidual[x][i] -= fluxDrum;
            rezidual[i][x] += fluxDrum;
        }

        fluxMaxim += fluxDrum;
    }
    return fluxMaxim;
}



int main()
{
    ofstream fout("maxflow.out");
    vector<vector<pair<int, int>>> lisAdiacenta;
    Citire(lisAdiacenta);
    vector<int> tati;
    fout << ElmondsKarp(lisAdiacenta, 1, lisAdiacenta.size()-1, 110005);
    return 0;
}