#include <bits/stdc++.h>//Goldberg-Tarjan (Push-relabel algorithm)
using namespace std;

ifstream fin ("maxflow.in");
ofstream fout("maxflow.out");

const int dim=1009,inf=1e9;

int n,m;
int flow[dim][dim];
int capacity[dim][dim];
int height[dim],excess[dim],seen[dim];

queue<int>excess_vertices;

void push(int x,int y){
    int d=min(excess[x],capacity[x][y]-flow[x][y]);
    flow[x][y]+=d;
    flow[y][x]-=d;
    excess[x]-=d;
    excess[y]+=d;
    if(d&&excess[y]==d){
        excess_vertices.push(y);
    }
}

void relabel(int x){
    int d=inf;
    for(int i=1;i<=n;i++){
        if(capacity[x][i]-flow[x][i]>0){
            d=min(d,height[i]);
        }
    }
    if(d<inf){
        height[x]=d+1;
    }
}

void discharge(int x){
    while(excess[x]>0){
        if(seen[x]<=n){
            int y=seen[x];
            if(capacity[x][y]-flow[x][y]>0&&height[x]>height[y]){
                push(x,y);
            }else{
                seen[x]++;
            }
        }else{
            relabel(x);
            seen[x]=1;
        }
    }
}

signed main(){
        fin>>n>>m;
    for(int i=1;i<=m;i++){
        int x,y,c;
        fin>>x>>y>>c;
        capacity[x][y]=c;
    }
    height[1]=n;
    excess[1]=inf;
    for(int i=2;i<=n;i++){
        push(1,i);
    }
    for(int i=1;i<=n;i++){
        seen[i]=1;
    }
    while(!excess_vertices.empty()) {
        int x=excess_vertices.front();
        excess_vertices.pop();

        if(x!=1&&x!=n)
            discharge(x);
    }
    int max_flow=0;
    for(int i=1;i<=n;i++){
        max_flow+=flow[i][n];
    }
        fout<<max_flow;
}