/* 
 * File:   Fluxmaxim.cpp
 * Author: slycer
 *
 * Created on January 2, 2012, 4:42 PM
 */
#include <vector>
#include <cstdlib>
#include <fstream>
#include <iostream>

using namespace std;

class Nod {
public:

    Nod(int a, int b, int c) {
        this->a = a;
        this->b = b;
        this->c = c;
    }
    int a, b, c;
    Nod * frate;
};

class Graf {
public:
    int n;
    vector<Nod * > *data;
    bool * marcat;
    Nod ** back;

    Graf(int n) {
        this->n = n;
        data = new vector<Nod*>[n + 1];
        marcat = new bool[n + 1];
        back = new Nod *[n + 1];
    }

    void add(int a, int b, int c) {
        Nod * unu = new Nod(a, b, c);
        Nod * doi = new Nod(b, a, 0);
        unu->frate = doi;
        doi->frate = unu;
        data[a].push_back(unu);
        data[b].push_back(doi);
    }

    int push_flow(int start, int destinatie) {
        int ret = 0;
        vector<int> q;
        for (int i = 0; i <= n; i++) {
            marcat[i] = false;
        }
        q.push_back(start);
        marcat[start] = true;
        back[start] = NULL;
        while (q.size() > 0) {
            //  cout << q.size() << "\n";
            int c = q.back();
            q.pop_back();

            for (vector<Nod*>::iterator i = data[c].begin(); i != data[c].end(); i++) {
                int next = (*i)->b;
                int cost = (*i)->c;
                if ((!marcat[ next ] && next != destinatie) && cost > 0) {
                    back[ next ] = (*i);
                    marcat[ next ] = true;
                    q.push_back(next);
                }
            }
        }

        for (vector<Nod*>::iterator i = data[destinatie].begin(); i != data[destinatie].end(); i++) {
            Nod *original = (*i)->frate;
            if ( marcat[ original->a ] && original->c > 0) {
                int minim = original->c;
                Nod * current = back[original->a];
                while (current != NULL) {
                    minim = min(current->c, minim);
                    current = back[current->a];
                }
                if (minim > 0 ) {
                    ret += minim;
                    Nod * current = back[original->a];
                    original->c -= minim; 
                    original->frate->c += minim; 
                    while (current != NULL) {
                        current->c -= minim; 
                        current->frate->c += minim; 
                        current = back[current->a];
                    }
                }
            }
        }

        return ret;
    }
};

/*
 * 
 */
int main(int argc, char** argv) {
    ifstream input("maxflow.in");
    ofstream output("maxflow.out");

    int n, m;
    input >> n >> m;
    Graf g(n);
    for (int i = 0; i < m; i++) {
        int a, b, c;
        input >> a >> b >> c;
        g.add(a, b, c);
    }

    int sol = 0;
    int c = 0;
    while ((c = g.push_flow(1, n)) > 0) {
        sol += c;
      //  cout << sol << endl; 
    }

    output << sol;

    return 0;
}