///O(n*m*m)
#include <iostream>
#include <vector>
#include <fstream>
#include <queue>
#include <numeric>
#define INFINITY 999999999

using namespace std;
class Graf{
private:
    int noNodes;
    int noEdges;
    vector<vector<int>> graf;
    vector<vector<pair<int, int>>> graf_c;
    bool fromZero;
    bool oriented;
    bool hasCosts;
private:
    bool constructSTNesaturatedBF(int s, int t, vector<vector<int>>& f,
                                  vector<vector<pair<int, int>>>& graf_t, vector<int>& tata, int& ip);
    void revizFlux(int s, int t, vector<vector<int>>& f, vector<int>& tata, int& ip);
public:
    Graf(int noNodes_, int noEdges_, const vector<vector<int>>& edges, bool fromZero_, bool oriented_, bool hasCosts_);
    int EndmondsKarp();
    ~Graf() = default;
};
void citireFisier(int &n, int &m, vector<vector<int>>& G);
void testEdmondsKarp(Graf mygraf);

int main() {
    int n, m; vector<vector<int>> G;
    citireFisier(n, m, G);
    Graf mygraf{n, m, G, false, true, true};
    testEdmondsKarp(mygraf);
    return 0;
}

void citireFisier(int &n, int &m, vector<vector<int>>& G){
    int x, y, z;
    ifstream fin("maxflow.in");
    fin>>n>>m;
    for(int i = 0; i < m; ++i){
        fin>>x>>y>>z;
        G.push_back({x, y, z});
    }
    fin.close();
}

void testEdmondsKarp(Graf mygraf){
    ofstream fout("maxflow.out");
    fout<<mygraf.EndmondsKarp();
    fout.close();
}
Graf::Graf(int noNodes_, int noEdges_, const vector<vector<int>> &edges, bool fromZero_, bool oriented_, bool hasCosts_) {
    noNodes = noNodes_;
    noEdges = noEdges_;
    fromZero = fromZero_;
    oriented = oriented_;
    hasCosts = hasCosts_;
    graf.resize(noNodes+1);
    if(hasCosts)
        graf_c.resize(noNodes+1);
    for(auto& edge:edges){
        int x = edge[0], y = edge[1];
        graf[x].push_back(y);
        if (!oriented)
            graf[y].push_back(x);
        if(hasCosts) {
            int z = edge[2];
            graf_c[x].push_back(make_pair(y, z));
            if (!oriented)
                graf_c[y].push_back(make_pair(x, z));
        }
    }
}
bool Graf::constructSTNesaturatedBF(int s, int t, vector<vector<int>>& f,
                                    vector<vector<pair<int, int>>>& graf_t, vector<int>& tata, int& ip){
    int i, v, c;
    vector<int> viz(noNodes + 1, 0);
    vector<int> minim(noNodes + 1, INFINITY);
    queue<int> C;
    C.push(s);
    viz[s] = 1;

    while(!C.empty()) {
        i = C.front();
        for(auto& j:graf_c[i]) {
            v = j.first; c = j.second;
            if (viz[v] == 0 && c > f[i][v]) { ///arc direct
                C.push(v);
                viz[v] = 1;
                tata[v] = i;
                minim[v] = min(minim[i], c - f[i][v]);
                if (v == t) {
                    ip = minim[t];
                    return true;
                }
            }
        }
        for(auto& j:graf_t[i]){
            v = j.first; c = j.second;
            if(viz[v] == 0 && f[v][i] > 0){   ///arc invers
                C.push(v);
                viz[v] = 1;
                tata[v] = -i;
                minim[v] = min(minim[i], f[i][v]);
                if(v == t){
                    ip = minim[t];
                    return true;
                }
            }
        }
        C.pop();
    }
    ip = -1;
    return false;
}
void Graf::revizFlux(int s, int t, vector<vector<int>>& f, vector<int>& tata, int& ip){
    int nod = t, parent, mod_nod;
    do{
        mod_nod = abs(nod);
        parent = abs(tata[mod_nod]);
        if(nod > 0){
            f[parent][mod_nod] += ip;
        }else{
            f[parent][mod_nod] -= ip;
        }
        nod = tata[mod_nod];
    }while(abs(nod) != s);
}
int Graf::EndmondsKarp(){
    short offset = fromZero?1:0;
    int s = 1 - offset, t = noNodes - offset, minim;
    vector<vector<int>> f(noNodes + 1, vector<int>(noNodes + 1, 0));
    vector<vector<pair<int, int>>> graf_t(noNodes + 1);
    vector<int> tata(noNodes + 1, 0);

    for(int i = 1 - offset; i <= noNodes - offset; ++i){
        for(auto& j:graf_c[i]){
            graf_t[j.first].push_back(make_pair(i, j.second));
        }
    }

    while(constructSTNesaturatedBF(s, t, f, graf_t, tata, minim)){
        revizFlux(s, t, f, tata, minim);
    }
    return accumulate(f[s].begin(), f[s].end(), 0);
}