#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 = 0x3f3f3f3f;

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

void citeste() {
    int a, b, c;
    f >> n >> m;
    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) {
            l = graf[nod].size();
            for (int i = 0; i < l; i++) {
                fiu = graf[nod][i];
                if (!vizitat[fiu] && F[nod][fiu] < cost[nod][fiu]) {
                    tata[fiu] = nod;
                    vizitat[fiu] = true;
                    Q.push(fiu);
                }
            }
        }
        else break;
    }
    return vizitat[n];
}

void flux() {
    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 (F[nod][n] == cost[nod][n] || !vizitat[nod]) continue;
            minim = INF;
            tata[n] = nod; nod = n;
            while (nod != 1) {
                ant = tata[nod];
                minim = min(minim, cost[ant][nod] - F[ant][nod]);
                nod = ant;
            }
            nod = n;
            while (nod != 1) {
                ant = tata[nod];
                F[ant][nod] += minim;
                F[nod][ant] -= minim;
                nod = ant;
            }

            sol += minim;
        }
    }
    g << sol << '\n';
}

int main() {
    citeste();
    flux();
}