#include <cstdio>
#include <vector>
#include <utility>
#include <cstring>
#include <queue>
#include <cmath>

using namespace std;

FILE *fin = fopen("maxflow.in","r");
FILE *fout = fopen("maxflow.out","w");

#define DIM 1005

int N, M, FluxMaxim, S, D;
int x, y, cost, FreqIesire[DIM], FreqIntrare[DIM], C[DIM][DIM], F[DIM][DIM];
vector <vector <pair <int, int> > >V;
int viz[DIM], St[DIM];

void Edmund_Karp();
int BFS();

int main() {
    fscanf(fin, "%d %d\n", &N, &M);

    V.resize(N + 2);
    for(int i = 1; i <= M; ++i) {
        fscanf(fin, "%d %d %d\n", &x, &y, &cost);

        V[x].push_back(make_pair(y, cost));

        FreqIesire[x]++;
        FreqIntrare[y]++;
        C[x][y] = cost;
    }

    S = 1, D = N;

    Edmund_Karp();

    for(int i = 1; i <= N; ++i) {
        FluxMaxim += F[i][D];
    }

    fprintf(fout, "%d\n", FluxMaxim);

    fclose(fin);
    fclose(fout);

    return 0;
}

void Edmund_Karp() {
    do {
        memset(viz, 0, sizeof(viz));

        if(BFS()) {
            return ;
        }

        St[1] = D;
        St[0] = 1;
        int a = 2e9, b = 2e9;

        while(St[St[0]] != S) {
            ++St[0];
            St[St[0]] = abs(viz[St[St[0] - 1]]);
            if(viz[St[St[0] - 1]] < 0) {
                b = min(b, F[St[St[0]]][St[St[0] - 1]]);
            }
            else {
                a = min(a, C[St[St[0]]][St[St[0] - 1]] - F[St[St[0]]][St[St[0] - 1]]);
            }
        }

        int v = min(a, b);

        for(int i = St[0]; i > 1; --i) {
            if(viz[St[St[0] - 1]] > 0) {
                F[St[St[0]]][St[St[0] - 1]] += v;
            }
            else {
                F[St[St[0]]][St[St[0] - 1]] -= v;
            }

            --St[0];
        }
    } while(1);
}

int BFS() {
    queue <int> Q;

    Q.push(S);
    viz[S] = S;

    while(!Q.empty()) {
        int x = Q.front();
        Q.pop();

        for(unsigned int z = 0; z < V[x].size(); ++z) {
            int p = V[x][z].first;
            if(viz[p] == 0 && C[x][p] > F[x][p]) {
                viz[p] = x;
                Q.push(p);
            }
            else {
                if(viz[p] == 0 && F[p][x] > 0) {
                    viz[p] = -x;
                    Q.push(p);
                }
            }
        }
    }

    return (viz[D] == 0);
}