//
// Created by avoro on 12/8/2025.
//
// flux maxim
// se da un graf rezidual sa se determine fluuxl maxim de la s la t
//graf rezidual -> un graf ponderat unde ponderea reprezinta o capacitate
///ford fulkerson
#include <iostream>
#include <fstream>
#include <vector>
#include <climits>
#include <queue>
#include <unordered_map>

using namespace std;
ifstream fin("maxflow.in");
ofstream fout("maxflow.out");


// vector<vector<int>> graf;
// unordered_map<int,unordered_map<int,int>> capac;
// vector<int> viz;
// vector<int> parent;
// int flux_total,flux;
// int n,m,x,y,c,s=1,t;
//
// void resetviz() {
//     for (int i = 1; i<=n; i++) {
//         viz[i] = 0;
//     }
// }

// int existaDrum(int nod, int p, int f) {
//     parent[nod] = p;
//     viz[nod] = 1;
//     if (nod == t) return f;
//     for (auto vecin: graf[nod]) {
//         if (viz[vecin] == 0 && capac[nod][vecin]>0) {
//             int flux_nou = min(f, capac[nod][vecin]);
//             int rez = existaDrum(vecin,nod,flux_nou);
//             if (rez >0 )
//                 return rez;
//         }
//     }
//     return 0;
// }
//
// int main() {
//     fin>>n>>m;
//     graf.resize(n+1);
//     viz.assign(n+1, 0);
//     parent.assign(n+1,-1);
//     for (int i = 1; i<=m ; i++) {
//         fin>>x>>y>>c;
//         graf[x].push_back(y);
//         graf[y].push_back(x); // muchie inversa pentru graful rezidual
//         capac[x][y] += c;
//         capac[y][x] += 0;
//     }
//     t = n;
//     flux = existaDrum(s,-1,INT_MAX);
//     while (flux > 0) {
//         resetviz();
//         flux_total+= flux;
//         int nod = t;
//         while (nod != s) {
//             int parinte = parent[nod];
//             capac[parinte][nod] -= flux;
//             capac[nod][parinte] +=flux;
//             nod = parinte;
//         }
//         flux = existaDrum(s,-1,INT_MAX);
//     }
//     fout<<flux_total<<'\n';
// }

unordered_map<int,unordered_map<int,int>> capac;

vector<vector<int>> graf;
vector<int> parent;
vector<int> viz;
int n,m,x,y,c,flux_max, flux,s,t;

void resetviz() {
    for (int i = 0; i<= n ; i++) {
        viz[i] = 0;
    }
}
int bfs() {
    resetviz();
    queue<int> q;
    q.push(s);
    viz[s] = 1;
    parent[s] = -1;

    while (!q.empty()) {
        int current = q.front();
        q.pop();

        for (auto vecin: graf[current]) {
            if (viz[vecin] == 0 && capac[current][vecin] > 0) {
                parent[vecin] = current;
                viz[vecin] = 1;
                q.push(vecin);

            }
        }
    }
    if (!viz[t]) return 0;
    int flux_drum = INT_MAX;
    for (int nod = t; nod !=s ; nod = parent[nod]) {
        int parinte = parent[nod];
        flux_drum = min(flux_drum,capac[parinte][nod]);
    }
    return flux_drum;
}

int main() {
    fin>>n>>m;
    parent.assign(n+1,-1);
    viz.assign(n+1,0);
    graf.resize(n+1);

    s = 1; t = n;
    for (int i = 0; i<m; i++) {
        fin>>x>>y>>c;
        graf[x].push_back(y);
        graf[y].push_back(x);
        capac[x][y] = c;
        capac[y][x] = 0;
    }

    flux = bfs();
    while (flux > 0) {
        flux_max += flux;

        int nod = t;
        while (nod != s) {
            int parinte = parent[nod];
            capac[parinte][nod] -= flux;
            capac[nod][parinte] += flux;
            nod = parinte;
        }
        flux = bfs();
    }
    fout<<flux_max;
}