#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>
#include <queue>

using namespace std;

/*
 * Codificarea pentru G este urmatoarea:
 * Primul int este varful;
 * Al doilea int este capacitatea arcului;
 * Al treilea int este fluxul;
*/
void citire(int &n, int &m, vector<pair<pair<int, int>, int>> *&G) {
    ifstream fin("maxflow.in");
    if(!fin.is_open()) {
        cout << "The file can't be opened!\n";
        exit(EXIT_FAILURE);
    }

    fin >> n >> m;
    G = new vector<pair<pair<int, int>, int>>[n + 1];
    for(int i = 0; i < m; ++i) {
        int x, y, z;
        fin >> x >> y >> z;
        G[x].push_back({{y, z}, 0});
    }

    fin.close();
}

int gaseste(vector<pair<pair<int, int>, int>> *G, int x, int y) {
    for(int i = 0; i < G[x].size(); ++i) {
        if(G[x][i].first.first == y)
            return i;
    }
    return -1;
}

/*
 * s -> sursa
 * t -> destinatia
 * tata -> vectorul de tati
 */

bool construieste_s_t_lant_nesaturat_BF(int s, int t, int *tata, vector<pair<pair<int, int>, int>> *G) {
    auto viz = new int[t + 1];
    fill(viz, viz + t + 1, 0);
    fill(tata, tata + t + 1, 0);

    queue<int> Q;
    Q.push(s);
    viz[s] = 1;
    while(!Q.empty()) {
        int u = Q.front();
        Q.pop();
        //cout << u << '\n';
        for(auto x : G[u]) {
            int v = x.first.first;
            int Cuv = x.first.second; //capacitatea de la u la v
            int Fuv = x.second; //fluxul de la u la v
            if(!viz[v] && Cuv - Fuv > 0) {
                Q.push(v);
                tata[v] = u;
                viz[v] = 1;
                if(v == t) {
                    return true;
                }
            }
            else if(!viz[v]) {
                int aux = gaseste(G, v, u);
                if(aux > -1 && G[v][aux].second > 0) { //daca exista arcul v-u si daca cap. reziduala  > 0
                    Q.push(v);
                    tata[v] = -u;
                    viz[v] = 1;
                    if(v == t) {
                        return true;
                    }
                }
            }

        }
    }

    return false;
}

/*
 * tata -> vectorul de tati pentru reconstituirea drumului
 * t -> destinatie din care se incepe reconstituirea
 * G -> Grafrul pentru a calcula IP
*/

int detIp(int *tata, int t, vector<pair<pair<int, int>, int>> *G) {
    int iP = (1e5);
    while(t) {
        //cout << t << ' ';
        if(tata[t] < 0) {
            int u = t;
            int v = -tata[t];
            int aux = gaseste(G, u, v);
            if(aux > -1 && G[u][aux].second < iP)
                iP = G[u][aux].second;
            t = -tata[t];
        }
        else {
            int u = t;
            int v = tata[t];
            int aux = gaseste(G, v, u);
            if(aux > -1 && G[v][aux].first.second - G[v][aux].second > 0 &&
               G[v][aux].first.second - G[v][aux].second < iP)
                iP = G[v][aux].first.second - G[v][aux].second;

            t = tata[t];
        }
    }
    return iP;
}

void revizuieste_flux(int *tata, int t, int iP, vector<pair<pair<int, int>, int>> *G) {
    while(t) {
        //cout << t << ' ';
        if(tata[t] < 0) {
            int u = t;
            int v = -tata[t];
            int aux = gaseste(G, u, v);
            if(aux > -1) {
                G[u][aux].second -= iP;
                //cout << G[u][aux].second << '\n';
            }
            t = -tata[t];
        }
        else {
            int u = t;
            int v = tata[t];
            int aux = gaseste(G, v, u);
            if(aux > -1) {
                G[v][aux].second += iP;
                //cout << G[v][aux].second << '\n';
            }
            t = tata[t];
        }
    }
}

int main() {
    int n, m;
    vector<pair<pair<int, int>, int>> *G;
    citire(n, m, G);
    auto tata = new int[n + 1];

    while(construieste_s_t_lant_nesaturat_BF(1, n, tata, G)) {
        int iP = detIp(tata, n, G);
        revizuieste_flux(tata, n, iP, G);
    }

    int flux = 0;
    for(auto x : G[1]) {
        flux += x.second;
    }
    ofstream fout("maxflow.out");
    fout << flux << '\n';
    delete[] G;
    return 0;
}