#include <iostream>
#include <fstream>
#include <queue>

using namespace std;
ifstream fin("maxflow.in");
ofstream fout("maxflow.out");
#define INTMAX (1<<30)

class muchie {
public:
    int v, f, c; // capatul muchiei, flux, capacitate
};

class muchie_reziduala {
public:
    int v, c;
};

void init(vector<vector<muchie>>& G, vector<vector<muchie_reziduala>>& Gr, vector<int>&e, vector<int>&h, int n, int s, int d) {
    int u;
    h[s] = n;
    for (auto& mu : G[s]) {
        e[mu.v] = mu.c;
        Gr[mu.v].push_back({ s, mu.c });
        //mu.f = mu.c;
        e[s] -= mu.c;
    }
    //graf rezidual
    for (u = 1; u <= n; u++) {
        for (const auto& mu : G[u]) {
            Gr[u].push_back(muchie_reziduala{mu.v, mu.c});
            Gr[mu.v].push_back(muchie_reziduala{ u, 0 });
        }
    }
}

void pompare(vector<vector<muchie_reziduala>>& Gr, vector<int>& e, int u, muchie_reziduala& v) {
    int delta = min(e[u], v.c);
    e[u] -= delta;
    e[v.v] += delta;
    v.c -= delta;
    for (auto& mu : Gr[v.v]) {
        if (mu.v == u) {
            mu.c += delta;
            break;
        }
    }
}

void inaltare(vector<int>& h, int u) {
    h[u] += 1;
}

int pompare_preflux(vector<vector<muchie>>& G, int n, int s, int d) {
    vector< vector<muchie_reziduala> >Gr(n+1); // size n
    vector<int>e( n+1, 0 ), h( n+1, 0 ); // exces si inaltime a nodurilor | init pe 0
    int u;
    bool pompat, aceeasi_stare;
    init(G, Gr, e, h, n, s, d);
    while (1) {
        aceeasi_stare = 1;
        for (u = 2; u <= n - 1; u++) {
            if (e[u] <= 0) // daca nu am exces
                continue;
            aceeasi_stare = 0;
            pompat = 0;
            for (auto& mu : Gr[u]) {
                if (mu.c <= 0) // nu exista muchia
                    continue;
                if (h[u] > h[mu.v]) {
                    pompat = 1;
                    pompare(Gr, e, u, mu);
                    continue;
                }
            }
            if (pompat == 0) {
                inaltare(h, u);
                continue;
            }
        }
        if (aceeasi_stare == 1)
            break;
    }
    return e[n];
}

int main() {
    vector< vector<muchie> >G; // {flux, capacitate}
    int n, m, i, x, y, z;
    fin >> n >> m;
    G.resize(n+1);
    for (i = 1; i <= m; i++) {
        fin >> x >> y >> z;
        G[x].push_back({y,0,z});
    }
    fout<<pompare_preflux(G, n, 1, n);
}

/*vector< vector<muchie> >Gr(n);
    vector<int>e( n );
    for (auto el : e) {
        cout << el << ' ';
    }
    i = 0;
    cout << G[4].empty();
    G[4].resize(2);
    cout<<G[4].empty();
    for (auto l : G) {
        cout << i++ << ": ";
        for (auto el : l) {
            cout << el.second<<' ';
        }
        cout << '\n';
    }*/