#include <fstream>
#include <vector>
#include <queue>
using namespace std;

ifstream f_cin("maxflow.in");
ofstream f_cout("maxflow.out");

// sursa de inspiratie : https://www.youtube.com/watch?v=ekmc-9Wgx3k si https://www.youtube.com/watch?v=a0XlX0NwRhM

// Folosim BFS pentru a gasi un drum de la start la nodul sink
// avem nenvoie de graful rezidual pentru ca Ford-Fulkerson sa atinga solutia optima
// si acest lucru ne va permite sa updatam cu un flux mai bun muchiile odata parcurse

// matricea de capacitati contine ulterior si sensul invers de muchii, util in graful rezidual
// odata ce am un path cu min de flow gasit prin BFS il folosesc mai departe sa obtin graful rezidual pe acel path
// e util sa parcurg cu nodul destinatie folosind-ma de parinti pentru graful rezidual


//int capacitati[1001][1001]; //--> mai bine ulterior cu assign pe size-ul care imi trebuie

vector<vector<int>>capacitati;
int n;
vector<vector<int>>adj_list;
//vector<vector<int>>capacitati;

int bfs_residual(int s,int t,vector<int>&parinte){ // s- nodul sursa si t- nodul de sink/destinatie
    for(int &j : parinte)
        j = -1; // initialiez vectorul de parinti cu o val neg
    queue<pair<int,int>> q_bfs; // am coada specifica BFS-ului

    parinte[s] = -2; // nodul de start nu are parinte si initilizez aici cu val cea mai mica
    q_bfs.push({s,110001}); // coada va avea 2 comp per fiecare elem: nod si capacitatea (care va fi un numar natural in intervalul [1, 110 000])


    while(!q_bfs.empty()) {
        int nod_i = q_bfs.front().first;
        int flux = q_bfs.front().second;
        q_bfs.pop();

        for (auto nod: adj_list[nod_i]) {  //parcurg vecinii nodului curent si sa am capacitate pe muchia (i, nod din adj_list)
            // are sens sa caut path ce nu contine muchii saturate (care sunt luate in calcul pe taietura minima)

            if (parinte[nod] == -1 && capacitati[nod_i][nod]) { // in capacitati dupa ce am facut primul update de BFS capacitati[nod_i][nod] ar putea avea capac. reziduala si daca este 0 atunci e muchie saturata si va cauta pe un alt vecin
                parinte[nod] = nod_i;

                int new_flux = min(flux, capacitati[nod_i][nod]);  // fluxul va fi modificat cu minimul
                if (nod == t) // daca am ajuns la sink node atunci preiau noul flux
                    return new_flux;
                q_bfs.push({nod, new_flux});

            }
        }
    }
    return 0;
}


int flux_maxim(int sursa,int destinatie){
    int flux_max = 0, flux;
    vector<int>parinte(n+1);
    flux = bfs_residual(sursa, destinatie, parinte);


    while(flux){
        flux_max += flux; // cumulez fluxul
        int nod_curent = destinatie;
        while(nod_curent != sursa){
            int prev=parinte[nod_curent];

            if  (capacitati[nod_curent][prev] <0) {
                capacitati[nod_curent][prev] += flux + 1;// cu cat as decrementa ca flux pe muchie in sens invers
            }
            else {
                capacitati[nod_curent][prev] += flux;
            }

            capacitati[prev][nod_curent]-=flux;// aici avem capacit_reziduala = capacitate- min de flux pe path
            nod_curent=prev;
        }
        flux = bfs_residual(sursa, destinatie, parinte);
    }
    return flux_max;
}


int main() {
    int m, u, v, c; // m fiind nr  de muchii iar c fiind val per muchie=capacitatea

//    preluare inputuri
    f_cin >> n >> m;
    adj_list.resize(n + 1);
    capacitati.assign(n+1, vector<int>(n+1, -1));


    for (int i = 1; i <= m; ++i) {
        f_cin >> u >> v >> c;
        capacitati[u][v] = c;
        adj_list[u].push_back(v);
        adj_list[v].push_back(u);
    }
    f_cout << flux_maxim(1, n)<<endl;
//    return 0;
}