#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;

vector<int>adj[dim];

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

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;
}

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

vector<int>find_max_height_vertices(){
    vector<int>max_height;
    for(int i=2;i<n;i++){
        if(excess[i]>0){
            if(!max_height.empty()&&height[i]>height[max_height[0]]){
                max_height.clear();
            }
            if(max_height.empty()||height[i]==height[max_height[0]]){
                max_height.push_back(i);
            }
        }
    }
    return max_height;
}

signed main(){
        fin>>n>>m;
    for(int i=1;i<=m;i++){
        int x,y,c;
        fin>>x>>y>>c;
        adj[x].push_back(y);
        adj[y].push_back(x);
        capacity[x][y]=c;
    }
    height[1]=n;
    excess[1]=inf;
    for(int i:adj[1]){
        push(1,i);
    }
    vector<int>current;
    while(!(current=find_max_height_vertices()).empty()){
        for(int x:current){
            bool pushed=false;
            for(int y:adj[x]){
                if(capacity[x][y]-flow[x][y]>0&&height[x]==height[y]+1){
                    push(x,y);
                    pushed=true;
                }
                if(excess[x]==0){
                    break;
                }
            }
            if(!pushed){
                relabel(x);
                break;
            }
        }
    }

    int max_flow=0;
    for(int i:adj[n]){
        max_flow+=flow[i][n];
    }
        fout<<max_flow;
}