#include <fstream>
#include <list>
#include <bitset>
#define DIM 1011
using namespace std;
ifstream f("maxflow.in");
ofstream g("maxflow.out");
int N,M;
int F[DIM][DIM],C[DIM][DIM];
int q[DIM+11],T[DIM];
long long sol;

list<int> L[DIM];
bitset<DIM> viz;

inline int bfs(){
    int p,u,nod;
    list<int>::iterator it;
    viz.reset();

    p=u=1,q[1]=1;
    while(p<=u){
        nod=q[p],viz[nod]=1;
        for(it=L[nod].begin();it!=L[nod].end();it++){
            if(!viz[*it] && C[nod][*it]>F[nod][*it]){
                q[++u]=*it;
                viz[*it]=1;
                T[*it]=nod;
            }
        }
        p++;
    }
    return viz[N];
}

int main(void){
    register int i,j,x,y,c,minim;
    list<int>::iterator it;

    f>>N>>M;
    for(i=1;i<=M;i++){
        f>>x>>y>>c;
        L[x].push_back(y);
        L[y].push_back(x);
        C[x][y]=c;
    }


    while(bfs()){
        for(it=L[N].begin();it!=L[N].end();it++){
            if(viz[*it] && C[*it][N]>F[*it][N]){
                x=*it,minim=C[*it][N]-F[*it][N];
                while(T[x]) minim=min(minim,C[T[x]][x]-F[T[x]][x]),x=T[x];
                x=*it;
                F[x][N]+=minim,F[N][x]-=minim;
                while(T[x]) F[T[x]][x]+=minim,F[x][T[x]]-=minim,x=T[x];
                sol+=minim;
            }
        }
    }

    g<<sol;
    f.close();
    g.close();
    return 0;
}