#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],seen[dim];

priority_queue<pair<int,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({height[y],y});
    }
}

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

void discharge(int x){
    while(excess[x]>0){
        bool ok=false;
        for(int y:adj[x]){
            if(capacity[x][y]-flow[x][y]>0&&height[x]>height[y]){
                ok=true;
                push(x,y);
            }
            if(excess[x]<=0){
                return;
            }
        }
        if(!ok){
            relabel(x);
        }
    }
}

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);
    }
    while(!excess_vertices.empty()) {
        int x=excess_vertices.top().second;
        excess_vertices.pop();
        if(x!=1&&x!=n)
            discharge(x);
    }
    int max_flow=0;
    for(int i:adj[n]){
        max_flow+=flow[i][n];
    }
        fout<<max_flow;
}