#include<cstdio>
#include<cstring>
int min2(int a,int b){
    if(a<b)
        return a;
    return b;
}
const int N=1000;
const int M=5000;
class To{
    public:
        int v,nxt,can;
};
To g[2*M+1];
int start[N+1];
bool vis[N+1];
int where[N+1];
int imp[N+1];
int q[N+1];
int ton[N+1];
int n,m,p,nimp,f;
void add_edge(int x,int y,int z){
    g[p].v=y;
    g[p].nxt=start[x];
    g[p].can=z;
    start[x]=p++;
}
void bfs(){
    int l=1,r=1;
    q[1]=1;
    memset(vis,0,sizeof(vis));
    vis[1]=true;
    vis[n]=true;
    while(l<=r){
        int dad=q[l++];
        for(int i=start[dad];i>=0;i=g[i].nxt){
            To son=g[i];
            if(!vis[son.v]&&son.can){
                vis[son.v]=true;
                q[++r]=son.v;
                where[son.v]=i;
            }
        }
    }
}
void update(int node){
    int cnode=node;
    f=g[ton[node]].can;
    while(node!=1){
        f=min2(f,g[where[node]].can);
        node=g[where[node]^1].v;
    }
    node=cnode;
    g[ton[node]].can-=f;
    while(node!=1){
        g[where[node]].can-=f;
        g[where[node]^1].can+=f;
        node=g[where[node]^1].v;
    }
}
int main(){
    freopen("maxflow.in","r",stdin);
    freopen("maxflow.out","w",stdout);
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
        start[i]=-1;
    for(int i=1;i<=m;i++){
        int x,y,z;
        scanf("%d%d%d",&x,&y,&z);
        add_edge(x,y,z);
        if(y==n){
            imp[++nimp]=x;
            ton[x]=p-1;
        }
        add_edge(y,x,0);
    }
    int flow=0;
    bool flag=true;
    while(flag){
        flag=false;
        bfs();
        for(int i=1;i<=nimp;i++){
            if(vis[imp[i]]){
                update(imp[i]);
                flow+=f;
                flag=true;
            }
        }
    }
    printf("%d",flow);
    return 0;
}