#include<bits/stdc++.h>
using namespace std;
ifstream fin("maxflow.in");
ofstream fout("maxflow.out");
int const N = 1001 , inf = (1 << 30);
int gr[N][N] , gl[N][N] , n , m;
int niv[N] , maxflow , t[N] , viz[N];
bool am;
void getgl(){
    fill(niv , niv + 1 + n , 0);
    fill(viz , viz + 1 + n , 0);
    queue<int> q;
    q.push(1);
    viz[1] = 1;
    while(!q.empty()){
        int node = q.front();
        q.pop();
        for(int y = 1 ; y <= n ; ++ y){
            if(gr[node][y] && !viz[y]){
                niv[y] = 1 + niv[node];
                viz[y] = 1;
                q.push(y);
            }
        }
    }
    for(int i = 1 ; i <= n ; ++ i){
        for(int j = 1 ; j <= n ; ++ j){
            if(niv[i] + 1 == niv[j])
                gl[i][j] = gr[i][j];
            else
                gl[i][j] = 0;
        }
    }
}
bool ok;
int flow;
void dfs(int node , int g){
    if(ok)
        return;
    if(node == n){
        ok = true;
        flow = g;
        return;
    }
    for(int i = 1 ; i <= n ; ++ i)
        if(gl[node][i]){
            t[i] = node;
            dfs(i , min(g , gl[node][i]));
        }
}
void Dinic(){
    getgl();
    ok = false;
    dfs(1 , inf);
    while(flow){
        int x = n;
        maxflow += flow;
        while(t[x]){
            gr[t[x]][x] -= flow;
            x = t[x];
        }
        getgl();
        ok = false;
        dfs(1 , inf);
        if(!ok)
            flow = 0;
    }
}
int main(){
    fin >> n >> m;
    for(int i = 1 ; i <= m ; ++ i){
        int a , b , c;
        fin >> a >> b >> c;
        gr[a][b] = c;
    }
    Dinic();
    fout << maxflow;
    return 0;
}