#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;
    viz[Source] = true;

    while (st <= dr) {
        int x = Q[st++];
        if (x == Dest)  // excludem destinatia pt optimizare: amelioram astfel mai multe drumuri din aceeasi parcurgere BFS
            continue;

        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);
        //Capacity[y][x] = 0;
    }
    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), care exclude destinatia
        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 capacitatea reziduala minima
                flowgap = min(flowgap, Capacity[T[x]][x] - Flow[T[x]][x]);

            //amelioram fluxul lantului
            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;
}