#include <iostream>
#include <fstream>
#include <vector>
#include <queue>

using namespace std;

const int INF = 110001;

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

int n, m;
int capacitate[1001][1001];
vector<int>tata, viz;
vector<int>graf[1001];
queue<int>q;

//functia BF cauta un drum in graful initial de la sursa catre capat
//daca-l gaseste, returneaza 1, altfel 0

int BF()
{
    viz.assign(n+1, 0);
    tata.assign(n+1, 0);
    while(!q.empty())
        q.pop();

    q.push(1);
    viz[1]=1;
    tata[1]=1;

    while(!q.empty())
    {
        int nod=q.front();
        q.pop();

        if(nod==n) continue;

        for(auto j:graf[nod])
        {
            if(viz[j]==0 && capacitate[nod][j]>0)
            {
                q.push(j);
                tata[j]=nod;
                viz[j]=1;
            }
        }
    }
    return viz[n];
}

int main()
{
    f>>n>>m;
    int x,y,c,flowmaxim;
    //citim si cream graful si capacitatea sa
    for(int i=1; i<=m; i++)
    {
        // muchie de la x la y cu capacitatea c
        f>>x>>y>>c;
        capacitate[x][y] = c;
        graf[x].push_back(y);
        graf[y].push_back(x);
    }
    while(BF()) // cat timp exista un lant nevizitat de la sursa la destinatie
    {
        for(auto nod: graf[n])
        {
            if(!viz[nod]) continue;

            tata[n]=nod;
            int flow=INF;

            // cautam valoarea minima cu care putem creste fluxul de pe drumul de la sursa la destinatie
            for(nod=n; nod!=1; nod=tata[nod])
                flow=min(flow, capacitate[tata[nod]][nod]);

            if(flow==0) continue;

            for(nod=n; nod!=1; nod=tata[nod])
            {
                capacitate[tata[nod]][nod]-=flow; // capacitatea muchiei din graful initial scade
                capacitate[nod][tata[nod]]+=flow; // capacitatea muchiei inverse creste
            }
            flowmaxim+=flow;
        }

    }
    g<<flowmaxim;
    return 0;
}

// Complexitate: O(n*3) unde n este numarul de noduri

//Algoritmul este o implementare a alg Ford-Fulkerson pentru a gasi
//flow-ul maxim intr-o retea. Alg FF se bazeaza pe o metoda iterativa pentru
//a gasi flow-ul maxim intr-o retea. Incepe cu un flow initial si-l creste,
//pana cand nu mai poate adauga nimic la el. Algoritmul se foloseste
//de parcurgerea BFS pentru a gasi un drum de la sursa la destinatie in
//graful initial si apooi creste flow-ul pe parcursul acestui drum
//Codul de bazeaza pe parcurgerea BFS, care returneaza 1 daca exista un drum
//nevizitat, altfel returneaza 0. BF() utilizeaza o coada pentru a realiza
//parcurgerea, iar reprezentarea grafului se realizeaza printr-o lista de
//adiacenta, in array-ul graf.
//in viz retinem nodurile vizitate, iar in tata retinem tatal fecarui nod
//in main, in loop-ul de while, incepem prin a apela functia BF(), iar
//daca aceasta returneaza 1, continuam while ul. in while, folosim vectorul
//de tati pentru a calcula valoarea minima cu care putem creste flow-ul de-a
//lungul drumului in BF(). Odata gasit, crestem flow-ul si updatam vectorul
//ce-mi retine capacitatile