#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] , n , m;
int niv[N] , maxflow , t[N] , viz[N];
pair<int , int>e[5 * N];
vector<int> Gr[N] , gl[N];
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(auto y : Gr[node])
            if(gr[node][y] && !viz[y]){
                niv[y] = 1 + niv[node];
                viz[y] = 1;
                q.push(y);
            }
    }
    for(int i = 1; i <= n ; ++ i)
        gl[i].clear();
    for(int i = 1 ; i <= m ; ++ i){
        int a , b;
        tie(a , b) = e[i];
        if(niv[a] == 1 + niv[b])
            gl[b].push_back(a);
        if(niv[a] + 1 == niv[b])
            gl[a].push_back(b);
    }
}
bool ok;
int flow;
void dfs(int node , int g){
    if(ok)
        return;
    if(node == n){
        ok = true;
        flow = g;
        return;
    }
    for(auto y : gl[node])
        if(gr[node][y]){
            t[y] = node;
            dfs(y , min(g , gr[node][y]));
        }
}
void Dinic(){
    getgl();
    ok = false;
    dfs(1 , inf);
    while(flow){
        int x = n;
        maxflow += flow;
        while(t[x]){
            gr[t[x]][x] -= flow;
            gr[x][t[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;
        e[i] = make_pair(a , b);
        Gr[a].push_back(b);
        Gr[b].push_back(a);
        gr[a][b] = c;
    }
    Dinic();
    fout << maxflow;
    return 0;
}