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

using namespace std;

const int nMax = 1001;
const int mMax = 1001;

int n, m, sursa, destinatie, fluxTotal;

int capacitate[nMax][mMax];
int flux[nMax][mMax];

int tata[nMax];
vector<vector<int>>vecini;
vector<bool> vizitat;

void Citire()
{
    ifstream f("maxflow.in");

    f >> n >> m;

    vecini.resize(n + 1);
    vizitat.resize(n + 1);

    sursa = 1;
    destinatie = n;

    int x, y, z;

    for(int i = 0; i < m; i++)
    {
        f >> x >> y >> z;

        vecini[x].push_back(y);
        vecini[y].push_back(x);
        capacitate[x][y] += z;
    }
}

// Un bfs in care returnez: 
//          - 1, daca exista drum de la sursa la destinatie prin am flux
//          - 0, daca nu exista drum de la sursa la destinatie

int Bfs()
{
    fill(vizitat.begin(), vizitat.end(), false);
    queue<int> coada;

    coada.push(sursa);
    vizitat[sursa] = true;

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

        if(nodCurent == destinatie)
            continue;

        for(auto vecin : vecini[nodCurent])
        {
            if(vizitat[vecin] || flux[nodCurent][vecin] == capacitate[nodCurent][vecin])
                continue;
            
            coada.push(vecin);
            vizitat[vecin] = true;
            tata[vecin] = nodCurent;
        }
    }
    return vizitat[destinatie];
}

// Determin min(capacitatea ramasa a fiecarui nod din drumul de la sursa la destinatie)
int CapacitateRamasaMinima()
{
    int minim = 10000000;

    for(int nod = destinatie; nod != sursa; nod = tata[nod])
    {
        minim = min(minim, capacitate[tata[nod]][nod] - flux[tata[nod]][nod]);
    }

    return minim;
}

void ActualizareFlux(int capacitateaRamasa)
{
    for(int nod = destinatie; nod != sursa; nod = tata[nod])
    {
        flux[tata[nod]][nod] += capacitateaRamasa;
        flux[nod][tata[nod]] -= capacitateaRamasa;
    }
}

void DeterminareFuxMaxim()
{
    while(Bfs())
    {
        for(auto vecin : vecini[destinatie])
        {
            if(!vizitat[vecin] || flux[vecin][destinatie] == capacitate[vecin][destinatie])
                continue;

            tata[destinatie] = vecin;

            int capacitateRamasaMin = CapacitateRamasaMinima();

            if(capacitateRamasaMin == 0)
                continue;

            ActualizareFlux(capacitateRamasaMin);  

            fluxTotal += capacitateRamasaMin;   
        }
    }
}

void Afisare()
{
    ofstream g("maxflow.out");
    g << fluxTotal;
}

int main()
{   
    Citire();
    DeterminareFuxMaxim();
    Afisare();

    return 0;
}