#include <iostream>
#include <fstream>
#include <vector>
#include <cmath>
#include <iomanip>
#include <climits>
#include <queue>

using namespace std;

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

int n, m;
vector<vector<int>> lista_adiacenta; //lista de adiacenta a grafului
vector<vector<int>> graf_rezid; //pentru a retine capacitatea folosita intr-un anumit moment pentru o muchie

vector<int> vizit;
vector<int> tata;

bool BFS()
{
    queue<int> vecini;

    tata.clear();
    tata.resize(n+1, 0);

    vizit.clear();
    vizit.resize(n+1, 0);

    vecini.push(1);
    vizit[1] = 1;

    while(!vecini.empty()){
        int nod_curent = vecini.front();
        vecini.pop();

        if (nod_curent == n) break; //am ajuns la final

        for (auto it: lista_adiacenta[nod_curent]){
            if (!vizit[it] and graf_rezid[nod_curent][it] > 0){ //daca nu am trecut prin acel nod si capacitatea sa imi permite sa trec, atunci ma duc
                tata[it] = nod_curent; //ca sa retin drumul facut
                vecini.push(it);
                vizit[it] = 1;
            }
        }
    }
    return vizit[n]; //vizit[n] va fi true doar daca pot ajunge de la nodul 1 la nodul n
}


void EdmondsKarp()
{
    int flux_max = 0;
    while (BFS()){ //cat timp am drum de la sursa pana la final
        for (auto it: lista_adiacenta[n]){ //iau vecinii nodului final
            if (vizit[it] and graf_rezid[it][n] > 0){
                int flux_curent = graf_rezid[it][n]; ///pornesc cu fluxul egal cu capacitatea vecinului lui n
                for (int i = it; i != 1; i = tata[i]){ ///parcurg drumul spre nodul 1
                    flux_curent = min(flux_curent, graf_rezid[tata[i]][i]); //actualizez fluxul in functie de capacitatea nodurilor pe care le intalnesc in drumul meu
                }

                //actualizez graful rezidual
                graf_rezid[it][n] -= flux_curent;
                graf_rezid[n][it] += flux_curent;

                for (int i = it; i != 1; i = tata[i]){
                    graf_rezid[tata[i]][i] -= flux_curent;
                    graf_rezid[i][tata[i]] += flux_curent;
                }

                //adaug fluxul curent la cel maxim
                flux_max += flux_curent;
            }
        }
    }

    fout << flux_max;
}

int main()
{
   fin >> n >> m;
   lista_adiacenta.resize(n+1);
   graf_rezid.resize(n+1, vector<int>(n+1, 0));

   for (int i = 1; i <= m; i++){
       int x, y, z;
       fin >> x >> y >> z;

       lista_adiacenta[x].push_back(y);
       lista_adiacenta[y].push_back(x); //pentru arcele inverse
       graf_rezid[x][y] = z; //retin capacitatea
   }

   EdmondsKarp();
}