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

using namespace std;

// ifstream fin ("input.txt");
// ofstream fout ("output.txt");

ifstream fin ("maxflow.in");
ofstream fout ("maxflow.out");

// !!!!! IMPORTANT !!!!!
// Problema daca se rezolva cu vectori este ineficienta
// Am observat ca este mai eficient sa folosesc arrayuri

int n, m;
int start, sink;
// de vizitare
bool viz[1010];
// Tati
int tat[1010];
// Matrice de adiacenta pentru graful rezidual
int vec[1010][1010];
long long maxFlux = 0;

// Folosim un bfs pentru a gasi un drum de la start la nodul sink
// Ne folosim de graful rezidual pentru ca Ford-Fulkerson este un algoritm de tip greedi
// iar acesta in unele cazuri nu produce solutia optima
// Asa ca ne folosim de muchiile reziduale pentru a ne putea intoarce intre noduri
// Functia returneaza true daca am gasit un drum de la start la nodul sink, altfel false

void read() {
    int x, y, c;
    for (int i = 1; i <= m; i++) {
        // fin >> nodul x >> nodul y >> capacitatea muchiei
        fin >> x >> y >> c;
        vec[x][y] = c;
    }
}

bool bfs() {
    // Trebuie sa resetez vectorul de vizitare
    memset(viz, false, sizeof(viz));
    memset(tat, 0, sizeof(tat));
    // Folosim un queue pentru a retine nodurile
    queue<int> q;
    // Pornesc intotdeauna de la nodul 1
    q.push(1);
    viz[1] = true;
    while (!q.empty()) {
        int curent = q.front();
        q.pop();

        if (curent == sink) {
            // Am gasit un drum de la start la nodul sink
            return true;
        }

        // Parcurgem vecinii nodului curent
        // Important este ca ne uitam daca este o muchie intre nodul curent si vecin,
        // indiferent daca muchia este cea reziduala sau nu
        for (int i = 1; i <= n; i++) {
            // Daca nu am vizitat vecinul si capacitatea muchiei (reziduala sau nu)
            // este mai mare decat fluxul muchiei respective
            if (!viz[i] && vec[curent][i] > 0) {
                // Adaugam vecinul in coada
                q.push(i);
                viz[i] = true;
                tat[i] = curent;
            }
        }
    }
    return false;
}

void dfs(int start)
        {
            viz[start] = true;
            for(int i = 1; i <= n; i++)
                if(!viz[i] && vec[start][i] > 0)
                    dfs(i);
        }

void maxflow() {
    // Cat timp exista un drum updatez fluxurile si graful rezidual
    while (bfs()) {
        // Optimizare

        /*
            De pe Infoarena:
            La fiecare pas construim arborele BFS (excluzand destinatia),
            si acum un drum de la sursa la destinatie e reprezentat de un drum de la sursa
            (care este radacina arborelui) la o frunza legata de destinatie printr-o muchie
            nesaturata. Astfel putem la un pas sa marim fluxul pe un numar maximal
            de astfel de drumuri, fara a mai reface BFS-ul.
            Aceasta optimizare reduce destul de mult timpul de executie.

        */
        for (int i = 1; i < n; i++) {
            if (viz[i] && vec[i][sink] > 0) {
                // Fluxul maxim este infinit
                int flux = 1000000000;
                tat[sink] = i;
                // Parcurg drumul de la nodul sink la nodul start (pentru ca in bfs am salvat tatal)
                // si gasesc fluxul maxim pe care il pot adauga

                for (int j = sink; tat[j] > 0; j = tat[j]) {
                    // Fluxul maxim este minimul dintre fluxul maxim si capacitatea muchiei
                    // de la nodul tatal la nodul curent
                    flux = min(flux, vec[tat[j]][j]);
                }
                // Daca fluxul este 0 nu mai am ce face
                if (flux == 0)
                    continue;
                // Parcurg din nou drumul de la nodul sink la nodul start
                // si updatez fluxurile si graful rezidual
                for (int j = sink; tat[j] > 0; j = tat[j]) {
                    // Updatez fluxul muchiei de la nodul tata la nodul curent
                    vec[tat[j]][j] -= flux;
                    // Updatez fluxul muchiei de la nodul curent la nodul tata
                    vec[j][tat[j]] += flux;
                }

                maxFlux += flux;
            }
        }
    }
    fout << maxFlux << '\n';

    // memset(viz, false, sizeof(viz));
    // dfs(start);

    // for (int i = 1; i <= n; i++)
    //     for (int j = 1; j <= n; j++)
    //         if (viz[i] && !viz[j] && vec[j][i])
    //             fout << i << " " << j << "\n";
}

int main() {
    // fin >> numarul de noduri >> numarul de muchii
    fin >> n >> m;
    // Nodul 1 este nodul start si nodul n este nodul sink
    start = 1;
    sink = n;
    read();
    maxflow();
    return 0;
}