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

using namespace std;

ifstream f ("maxflow.in");
ofstream g ("maxflow.out");

const int NMAX = 1000 + 1;
const int INF = (1 << 30);

int n, m;
int tata[NMAX];
bool vizitat[NMAX];
vector <int> graf[NMAX];
int cost[NMAX][NMAX], flux[NMAX][NMAX];

void citeste() {
    f >> n >> m;
    int a, b, c;
    for (int i = 1; i <= m; i++) {
        f >> a >> b >> c;
        graf[a].push_back(b);
        graf[b].push_back(a);
        cost[a][b] += c;
    }
}

bool BFS() {
    for (int i = 1; i <= n; i++) vizitat[i] = false;
    int nod, fiu, l;
    queue <int> Q;
    Q.push(1); vizitat[1] = true;
    while (!Q.empty()) {
        nod = Q.front(); Q.pop();
        if (nod == n) break;
        l = graf[nod].size();
        for (int i = 0; i < l; i++) {
            fiu = graf[nod][i];
            if (!vizitat[fiu] && flux[nod][fiu] < cost[nod][fiu]) {
                vizitat[fiu] = true;
                Q.push(fiu);
                tata[fiu] = nod;
            }
        }
    }
    return vizitat[n];
}

void flux_maxim() {
    int l, nod, ant, minim, sol = 0;
    while (BFS()) {
        l = graf[n].size();
        for (int i = 0; i < l; i++) {
            nod = graf[n][i];
            if (cost[nod][n] <= flux[nod][n] || !vizitat[nod]) continue;
            tata[n] = nod; nod = n;
            minim = INF;
            while (nod != 1) {
                ant = tata[nod];
                minim = min(minim, cost[ant][nod] - flux[ant][nod]);
                nod = ant;
            }
            nod = n;
            while (nod != 1) {
                ant = tata[nod];
                flux[ant][nod] += minim;
                flux[nod][ant] -= minim;
                nod = ant;
            }
            sol += minim;
        }
    }
    g << sol << '\n';
}

int main() {
    citeste();
    flux_maxim();
    return 0;
}