#include <stdio.h>
#define nmax 1000
#define mmax 5000

int n,m,prev[nmax+1],val[nmax+1][nmax+1],kcity[nmax+1][nmax+1],dq[nmax+1];

int min(int a,int b){
    if(a<=b) return a;
    else return b;
}

int BFS(int start,int finish){
    int i,elem,st,dr,ans=110000;
    for(i=1;i<=n;i++)
        prev[i]=-1;
    st=1;
    dr=1;
    prev[start]=0;
    dq[st]=start;
    while(st<=dr){
        elem=dq[st];
        for(i=1;i<=n;i++)
            if(kcity[elem][i]>=0&&prev[i]==-1&&val[elem][i]<kcity[elem][i]){
                prev[i]=elem;
                dr++;
                dq[dr]=i;
            }
        st++;
    }
    elem=finish;
    while(prev[elem]!=0){
        ans=min(ans,kcity[prev[elem]][elem]-val[prev[elem]][elem]);
        elem=prev[elem];
    }
    if(ans>0){
        elem=finish;
        while(prev[elem]!=0){
            val[prev[elem]][elem]=val[prev[elem]][elem]+ans;
            val[elem][prev[elem]]=-val[prev[elem]][elem];
            elem=prev[elem];
        }
    }
    return ans;
}

int main(){
    FILE *fin,*fout;
    fin=fopen("maxflow.in","r");
    fout=fopen("maxflow.out","w");
    int i,j,a,b,c,minim,start,finish,ans=0;
    fscanf(fin,"%d%d",&n,&m);
    for(i=1;i<=n;i++)
        for(j=1;j<=n;j++)
            kcity[i][j]=-1;
    for(i=1;i<=m;i++){
        fscanf(fin,"%d%d%d",&a,&b,&c);
        kcity[a][b]=c;
        kcity[b][a]=0;
    }
    start=1;
    finish=n;
    minim=BFS(start,finish);
    while(minim>0)
        minim=BFS(start,finish);
    for(i=1;i<=n;i++)
        ans+=val[start][i];
    fprintf(fout,"%d",ans);
    fclose(fin);
    fclose(fout);
    return 0;
}