#include <fstream>
#include <vector>

using namespace std;

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

const int N_MAX = 1000;
const int INF = 1000000000;

int N, M, Source, Dest;
vector<int> Edges[N_MAX + 1];
int Capacity[N_MAX + 1][N_MAX + 1], Flow[N_MAX + 1][N_MAX + 1];
int Q[N_MAX + 1], T[N_MAX + 1];
bool viz[N_MAX + 1];

bool BFS() {
    //initializare
    int st = 1, dr = 0;
    Q[++dr] = Source;
    for(int i = 1; i <= N; ++i)
        viz[i] = false;

    while(st <= dr) {
        int x = Q[st++];
        for(auto y : Edges[x]) {
            if(viz[y] || Capacity[x][y] == Flow[x][y])  //se face parcurgerea doar prin arcele nesaturate
                continue;

            viz[y] = true;
            Q[++dr] = y;
            T[y] = x;   //tatal lui y in arborele BFS
        }
    }

    return viz[Dest];   //daca BFS returneaza 0, inseamna ca nu am vizitat destinatia, deci nu mai avem ce ameliora, avem flux maxim
}

int main() {
    int x, y, c;
    in >> N >> M;
    for(int i = 1; i <= M; ++i) {
        in >> x >> y >> c;
        Edges[x].push_back(y);
        Capacity[x][y] = c;
        //formam graful rezidual: se adauga arcele inverse, cu capacitatea 0
        Edges[y].push_back(x);
    }
    Source = 1, Dest = N;

    int maxflow = 0;    //pornim cu fluxul 0 initial
    while(BFS())        //la fiecare pas cautam un lant de ameliorare (formate din arce nesaturate)
        for(auto x : Edges[Dest]) {    //luam frunzele arborelui BFS, care au arce direct in destinatie
            if(!viz[x] || Flow[x][Dest] == Capacity[x][Dest])   //trecem doar prin arborele BFS
                continue;

            int flowgap = INF;
            T[Dest] = x;
            for(x = Dest; x != Source; x = T[x])    //parcurgem invers lantul de ameliorare si determinam cu cat trebuie marit maxim fluxul
                flowgap = min(flowgap, Capacity[T[x]][x] - Flow[T[x]][x]);

            if(flowgap == 0)
                continue;

            //crestem fluxul pe fiecare arc al lantului de ameliorare (amelioram fluxul)
            for(x = Dest; x != Source; x = T[x]) {
                Flow[T[x]][x] += flowgap;   //se creste fluxul pe arcele retelei de transport
                Flow[x][T[x]] -= flowgap;   //se scade fluxul pe arcele grafului rezidual
            }
            maxflow += flowgap;
        }

    out << maxflow;

    return 0;
}