#include <iostream>
#include <fstream>
#include <queue>
#include <algorithm>
using namespace std;

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

int C[1005][1005],F[1005][1005],viz[1005],T[1005],n,m,s,d,ok;


void BF(int nod) {
    for(int i=1;i<=n;i++)
        viz[i]=T[i]=0;


    queue <int> q;

    q.push(nod);
    viz[nod]=1;

    while(!q.empty()) {
        int x=q.front(); q.pop();
        for(int i=1;i<=n;i++) {
            if(C[x][i]!=0 && viz[i]==0) {
                if(C[x][i]>F[x][i]) {
                    q.push(i);
                    viz[i]=1;
                    T[i]=x;

                    if(i==d) {ok=1; return;}
                }
            }
            if(C[i][x]!=0 && viz[i]==0) {
                if(F[i][x]>0) {
                    q.push(i);
                    viz[i]=1;
                    T[i]=x;
                }
            }
        }
    }
}

int main() {
    int v1,v2,v3;
    fin >> n >> m; s=1,d=n;
    while(fin >> v1 >> v2 >> v3) {
        C[v1][v2]=v3;
    }

    ok=1;
    int Minim,aux,l;
    while(ok!=0) {
        ok=0;
        BF(s);
        Minim=C[T[d]][d]-F[T[d]][d];

        aux=d,l=T[aux];
        while(l!=0) {
            if(C[l][aux]!=0) {
                if(C[l][aux]-F[l][aux]<Minim)
                    Minim=C[l][aux]-F[l][aux];
            }
            if(C[aux][l]!=0) {
                if(F[aux][l]<Minim)
                    Minim=C[l][aux]-F[l][aux];
            }
            aux=T[aux];
            l=T[aux];
        }
        aux=d,l=T[aux];
        while(l!=0) {
            if(C[l][aux]!=0)
                F[l][aux]+=Minim;
            if(C[aux][l]!=0)
                F[aux][l]-=Minim;

            aux=T[aux];
            l=T[aux];
        }
    }

    int S=0;
    for(int i=1;i<=n;i++)
        S+=F[i][d];
    fout << S;
    return 0;
}