#include<cstdio>
#include<bitset>
#include<queue>
#define N 1000
#define M 5000
using namespace std;

int lst[N+1];
int urm[2*M+1];
int vecin[2*M+1];

int c[N+1][N+1];
int f[N+1][N+1];
int n;

bitset<N+1> viz;
int tata[N+1];
int R;

int minim(int a,int b){
    return (a<b) ? a : b;
}

bool bfs(){
    viz.reset();

    int nod,i,p;
    queue<int> q;

    q.push(1);
    viz.set(1);

    while(!q.empty()){
        nod=q.front();
        if (nod==n) break ;
        q.pop();

        p=lst[nod];
        while(p!=0){
            i=vecin[p];
            if (c[nod][i]-f[nod][i]>0 &&viz[i]==false){
                viz.set(i);
                tata[i]=nod;
                q.push(i);
                if (i==n) break ;
            }
            p=urm[p];
        }
    }

    return viz[n];
}

void solve(){
    int i,min;

    while(bfs()){
        for(i=1;i<n;i++)
            if (c[i][n]-f[i][n]!=0 &&viz[i]==true){
                tata[n]=i;

                int nod=n;
                min=c[tata[nod]][nod]-f[tata[nod]][nod];
                while(nod!=1){
                    min=minim(min,c[tata[nod]][nod]-f[tata[nod]][nod]);
                    nod=tata[nod];
                }

                R+=min;
                nod=n;
                while(nod!=1){
                    f[tata[nod]][nod]+=min;
                    f[nod][tata[nod]]-=min;
                    nod=tata[nod];
                }
            }
    }
}

void adauga(int x,int y,int i){
    vecin[i*2-1]=y;
    urm[i*2-1]=lst[x];
    lst[x]=i*2-1;

    vecin[i*2]=x;
    urm[i*2]=lst[y];
    lst[y]=i*2;
}


int main(){
    freopen ("maxflow.in","r",stdin);
    freopen ("maxflow.out","w",stdout);
    int m,i,x,y;

    scanf ("%d%d",&n,&m);
    for(i=1;i<=m;i++){
        scanf ("%d%d",&x,&y);
        scanf ("%d",&c[x][y]);
        adauga(x,y,i);
    }

    solve();

    printf ("%d",R);
    return 0;
}