#include<fstream>
#include<cstring>
#include<queue>
#define max(a,b) ((a)>(b)?(a):(b))
#define min(a,b) ((a)<(b)?(a):(b))
#define foreach(G,x)
using namespace std;
ifstream in("maxflow.in");
ofstream out("maxflow.out");
const int Nmax = 1005;
const int Mmax = 5005;
int pred[Nmax],fr[Nmax];
int C[Nmax][Nmax],c[Nmax][Nmax];
int N,M;
queue<int> q;
struct list{
    int vf[Mmax],urm[Mmax],lst[Mmax],m;
    void push(int& x,int& y){
        vf[++m]=y;
        urm[m]=lst[x];
        lst[x]=m;
    }
} G,Gg;
int bfs(){
    while(!q.empty()) q.pop();
    memset(pred,0,sizeof(pred));
    q.push(1);
    pred[1]=-1;
    while(!q.empty()){
        int x=q.front(); q.pop();
        int it;
        for(int i=G.lst[x];i!=0;i=G.urm[i]){
            it=G.vf[i];
            if(pred[it]==0 && c[x][it]<C[x][it]){
                pred[it]=x;
                q.push(it);
                if(fr[it] && c[it][N]<C[it][N]){ pred[N]=it; return 1; }
            }
        }
        for(int i=Gg.lst[x];i!=0;i=Gg.urm[i]){
            it=Gg.vf[i];
            if(pred[it]==0 && c[x][it]<C[x][it]){
                pred[it]=x;
                q.push(it);
                if(fr[it] && c[it][N]<C[it][N]){ pred[N]=it; return 1; }
            }
        }
    }
    return 0;
}
int mark[Nmax],Fr[Nmax];
int addpath(int x){
    int y=x,Min=1<<30;
    while(y!=1){
        if(mark[y]) return 0;
        mark[y]=1;
        Min=min(Min,C[pred[y]][y]-c[pred[y]][y]);
        y=pred[y];
    }
    y=x;
    while(y!=1){
        c[pred[y]][y]+=Min;
        c[y][pred[y]]-=Min;
        y=pred[y];
    }
    return Min;
}
int main(){
    in>>N>>M;
    for(int i=1;i<=M;i++){
        int x,y,z;
        in>>x>>y>>z;
        G.push(x,y);
        Gg.push(y,x);
        if(y==N) fr[x]=1,Fr[++Fr[0]]=x;
        C[x][y]=z;
    }
    int MF=0;
    while(bfs()){
        for(int i=1;i<=Fr[0];i++){
            memset(mark,0,sizeof(mark));
            MF+=addpath(Fr[i]);
        }
    }
    out<<MF<<'\n';
    return 0;
}