#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;
    }

    for(int i = 1; i <= N; ++i) {
        if(FreqIntrare[i] == 0) {
            S = i;
            break;
        }
    }

    for(int i = 1; i <= N; ++i) {
        if(FreqIesire[i] == 0) {
            D = i;
            break;
        }
    }

    Edmund_Karp();

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

    fclose(fin);
    fclose(fout);

    return 0;
}

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

        if(BFS()) {
            return ;
        }

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

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

            nod = abs(viz[nod]);
        }

        nod = S;
        int v = min(a, b);
        FluxMaxim += v;

        while(St[0]) {
            F[nod][St[St[0]]] += v;
            nod = St[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) {
            if(viz[V[x][z].first] == 0 && C[x][V[x][z].first] > F[x][V[x][z].first]) {
                viz[V[x][z].first] = x;
                Q.push(V[x][z].first);
            }
            else {
                if(viz[V[x][z].first] == 0 && F[V[x][z].first][x]) {
                    viz[V[x][z].first] = -x;
                    Q.push(V[x][z].first);
                }
            }
        }
    }

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