///O(n*m*m)
#pragma GCC optimize ("O3")
#include <iostream>
#include <vector>
#include <fstream>
#include <queue>
#include <cstdio>
#define INFINITY 999999999
using namespace std;
int i, v, nod, parent;
int noNodes;
int noEdges;
vector<vector<pair<int, int>>> graf_c;
vector<vector<int>> f;
vector<vector<int>> graf_t;
vector<bool> viz;
vector<int> tata;
vector<vector<int>> c;
queue<int> C;

bool constructSTNesaturatedBF(int& s, int& t);
void revizFlux(int& s, int& t, int& ip);
int EndmondsKarp();
void citireFisier();
void testEdmondsKarp();

int main() {
    citireFisier();
    testEdmondsKarp();
    return 0;
}

void citireFisier(){
    int x, y, z;
    freopen("maxflow.in", "r", stdin);
    scanf("%d%d", &noNodes, &noEdges);

    graf_c.resize(noNodes+1);
    f.resize(noNodes + 1, vector<int>(noNodes + 1, 0));
    graf_t.resize(noNodes + 1);
    viz.resize(noNodes + 1, false);
    tata.resize(noNodes + 1, 0);
    c.resize(noNodes + 1, vector<int>(noNodes + 1, 0));
    for(int i = 0; i < noEdges; ++i){
        scanf("%d%d%d", &x, &y, &z);
        graf_c[x].push_back(make_pair(y, z));
        c[x][y] = z;
        graf_t[y].push_back(x);
    }
}

void testEdmondsKarp(){
    freopen("maxflow.out", "w", stdout);
    printf("%d", EndmondsKarp());
}

bool constructSTNesaturatedBF(int& s, int& t){
    fill(viz.begin(), viz.end(), false);
    C.push(s);
    viz[s] = true;

    while(!C.empty()) {
        i = C.front();
        for(auto& j:graf_c[i]) {
            v = j.first;
            if (!viz[v] && j.second > f[i][v]) { ///arc direct
                if(v != t)
                    C.push(v);
                viz[v] = true;
                tata[v] = i;
            }
        }
        for(auto& j:graf_t[i]){
            v = j;
            if(!viz[v] && f[v][i] > 0){   ///arc invers
                if(v != t)
                    C.push(v);
                viz[v] = true;
                tata[v] = -i;
            }
        }
        C.pop();
    }
    if(viz[t])
        return true;
    return false;
}
void revizFlux(int& s, int& t, int& ip){
    nod = t;
    do{
        nod = abs(nod);
        parent = tata[nod];
        if(parent >= 0){
            f[parent][nod] += ip;
        }else{
            f[nod][abs(parent)] -= ip;
        }
        nod = tata[nod];
    }while(abs(nod) != s);
}
int EndmondsKarp(){
    int s = 1, t = noNodes, minim;
    int sum = 0;
    while(constructSTNesaturatedBF(s, t)){
        for (auto& node: graf_t[t]) {
            if (f[node][t] == c[node][t] || !viz[node])
                continue;

            tata[t] = node;
            minim = INFINITY;

            nod = t;
            do{
                nod = abs(nod);
                parent = tata[nod];
                if(parent >= 0){
                    minim = min(minim, c[parent][nod] - f[parent][nod]);
                }else{
                    minim = min(minim, f[nod][abs(parent)]);
                }
                nod = tata[nod];
            }while(abs(nod) != s && minim != 0);
            if (minim == 0)
                continue;

            revizFlux(s, t, minim);
            sum += minim;
        }
    }
    return sum;
}