#include <iostream>
#include <fstream>
#include <algorithm>
#include <cmath>
#include <climits>
#include <queue>
#define INFILE "maxflow.in"
#define OUTFILE "maxflow.out"
#define INF INT_MAX
#define NMAX 1500
#define MMAX 5500

using namespace std;
ifstream in(INFILE);
ofstream out(OUTFILE);
int C[NMAX][NMAX];
int F[NMAX][NMAX];
int viz[NMAX];
int S,D;
int n,m;

void Read(){
    in>>n>>m;
    S=1;
    D=n;
    for(int i=1;i<=m;i++){
        int x,y,c;
        in>>x>>y>>c;
        C[x][y]=c;
    }

}

bool BFS(){
    queue<int> coada;
    viz[S]=1;
    coada.push(S);
    while(!coada.empty()&&viz[D]==0){
        int v=coada.front();
        coada.pop();
        for(int i=1;i<=n;i++){
            if(!viz[i]){
                if(F[v][i]<C[v][i]){
                    viz[i]=v;
                    coada.push(i);
                    //cout<<v<<endl;
                }
                else if(F[i][v]>0){
                    viz[i]=-v;
                    coada.push(i);
                    //cout<<-v<<endl;
                }
            }
        }
    }
    return !viz[D];
}

void FordFulkerson(){
    do{
        for(int i=1;i<=n;i++) viz[i]=0;
        if(BFS()) return;
        //cout<<"DA";
        int L[NMAX];
        L[0]=D;
        int a,b,v;
        a=INF; b=INF;
        int j=0;
        for(j=1;L[j-1]!=S;j++){
            L[j]=abs(viz[L[j-1]]);
            if(viz[L[j-1]]>0){
                a=min(a,C[L[j]][L[j-1]]-F[L[j]][L[j-1]]);
            }
            else if(viz[L[j-1]]<=0){
                b=min(b,F[L[j-1]][L[j]]);
            }
        }
        v=min(a,b);
        for(int i=j;i>0;i--){
            if(viz[L[i-1]]>0){
                F[L[i]][L[i-1]]+=v;
            }
            else if(viz[L[i-1]]<0){
                F[L[i-1]][L[i]]-=v;
            }
        }

    }while(true);
}

void Afisare(){
    int vf=0;
    for(int i=1;i<=n;i++) vf+=F[i][D];
    out<<vf;
}

int main()
{
    Read();
    FordFulkerson();
    Afisare();
    return 0;
}