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

vector<vector<pair<int, int>>> lisAdiacenta;

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

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

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

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

    tati[S] = -1;

    viz.clear();
    viz.resize(capacitati.size(), 0);
    viz[S] = 1;

    while(!coada.empty() && tati[T] == 0) {
        int x = coada.front();
        coada.pop();
        for(int v : rezidual[x]) {
            if(!viz[v] && capacitati[x][v] > flux[x][v]) {
                coada.push(v);
                tati[v] = x;
                viz[v] = 1;
            }
        }
    }
    return tati[T];
}



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

    vector<vector<int>> capacitati(lisAdiacenta.size(), vector<int>(lisAdiacenta.size(), 0));
    vector<vector<int>> flux(lisAdiacenta.size(), vector<int>(lisAdiacenta.size(), 0));
    vector<int> tati(lisAdiacenta.size(), 0);
    vector<bool> viz(lisAdiacenta.size(), 0);
    vector<vector<int>> rezidual(lisAdiacenta.size());

    for(int i = 0; i < lisAdiacenta.size(); ++i){
        for(int j = 0; j < lisAdiacenta[i].size(); ++j) {
            capacitati[i][lisAdiacenta[i][j].first] = lisAdiacenta[i][j].second;
            rezidual[i].push_back(lisAdiacenta[i][j].first);
            rezidual[lisAdiacenta[i][j].first].push_back(i);
        }
    }

    int fluxMaxim = 0;
    while(BFS_EK(capacitati, S, T, tati, flux, viz, rezidual) != 0) {
            for(int i : rezidual[T])
                if(viz[i] && flux[i][T] < capacitati[i][T]) {
                    tati[T] = i;
                    int fluxDrum  = capacitateMax;
                    for(int j = T; j != S; j = tati[j]) {
                        int x = tati[j];
                        fluxDrum = min(fluxDrum, capacitati[x][j]-flux[x][j]);
                    }
                    if(fluxDrum > 0) {
                        for(int j = T; j != S;j = tati[j]) {
                            int x = tati[j];
                            flux[x][j] += fluxDrum;
                            flux[j][x] -= fluxDrum;

                        }
                      fluxMaxim += fluxDrum;
                    }
                }
    }
    return fluxMaxim;
}


int main()
{
    ofstream fout("maxflow.out");

    Citire(lisAdiacenta);

    fout << maxFlow(lisAdiacenta, 1, lisAdiacenta.size()-1, 110005);
    return 0;
}