#include <bits/stdc++.h>
#define DIM 1010

using namespace std;

ifstream fin("maxflow.in");
ofstream fout("maxflow.out");

int fr[DIM], cost[DIM][DIM], flux[DIM][DIM], t[DIM];
vector<int> a[DIM];
deque<int> coada;

int n, m, x, y, z, sol;

int bfs() {
    memset(fr, 0, sizeof(fr));

    fr[1] = 1;
    coada.push_back(1);

    while (!coada.empty()) {
        int nod = coada.front();

        for (int vecin: a[nod])
            if (fr[vecin] == 0 && cost[nod][vecin] > flux[nod][vecin]) {
                coada.push_back(vecin);
                fr[vecin] = 1;
                t[vecin] = nod;
            }

        coada.pop_front();
    }

    return fr[n];
}

int main() {
    fin >> n >> m;
    while (fin >> x >> y >> z) {
        a[x].push_back(y);
        a[y].push_back(x);

        cost[x][y] = z;
    }

    while (bfs()) {
        for(int vecin: a[n])
            if (cost[vecin][n] > flux[vecin][n] && fr[vecin] == 1) {
                int minim = cost[vecin][n] - flux[vecin][n];
                x = vecin;

                for (;x!=1;x = t[x]) {
                    if (minim > cost[t[x]][x] - flux[t[x]][x])
                        minim = cost[t[x]][x] - flux[t[x]][x];
                }

                flux[vecin][n] += minim;
                flux[n][vecin] -= minim;

                x = vecin;

                for (;x!=1;x = t[x]) {
                   flux[t[x]][x] += minim;
                   flux[x][t[x]] -= minim;
                }

                sol += minim;
            }
    }

    fout << sol;
}