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

using namespace std;

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

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


class flux
{
    public:
        flux(int n, int m, int start, int end)
        {
            this -> n = n;
            this -> m = m;
            this -> start = start;
            this -> end = end;
            viz.resize(n + 1);
            vec.resize(n + 1);
            tat.resize(n + 1);
            for (int i = 1; i <= n; i++)
                vec[i].resize(n + 1);
        }
        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;
            }
        }

        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][n] > 0)
                    {
                        // Fluxul maxim este infinit
                        int flux = 1000000000;
                        // 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 i = end; i != start; i = tat[i])
                        {
                            // Fluxul maxim este minimul dintre fluxul maxim si capacitatea muchiei
                            // de la nodul tatal la nodul curent
                            flux = min(flux, vec[tat[i]][i]);
                        }

                        // Parcurg din nou drumul de la nodul sink la nodul start
                        // si updatez fluxurile si graful rezidual
                        for(int i = end; i != start; i = tat[i])
                        {
                            // Updatez fluxul muchiei de la nodul tata la nodul curent
                            vec[tat[i]][i] -= flux;
                            // Updatez fluxul muchiei de la nodul curent la nodul tata
                            vec[i][tat[i]] += flux;
                        }

                        maxFlow += flux;
                    }
                }
            }
            fout << maxFlow;

        }

    private:
        int n, m;
        // de vizitare
        vector <bool> viz;
        // Tati
        vector <int> tat;
        // Matrice de adiacenta pentru graful rezidual
        vector <vector <int> > vec;
        int start, end;
        int maxFlow = 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
        bool bfs()
        {
            // Trebuie sa resetez vectorul de vizitare
            fill(viz.begin(), viz.end(), false);
            fill(tat.begin(), tat.end(), 0);
            // 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 == end)
                {
                    // 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;
        }
};

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