#include <iostream>
#include <list>
#include <queue>
#include <stack>
#include <fstream>

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

const int NMAX = 1005, MMAX = 5005;
const int inf = 2147000000;

struct muchie{
    int d, c, f;
    muchie *anti;
} v[2*MMAX];

list<int> g[NMAX];
list<int>::iterator it;

int addflow(int N, int lvldg[])
{
    int plusflow, x, i, y, splusflow = 0;
    stack<int> st, stm;
    st.push(1);
    while(1){
        plusflow = inf;
        while(1){
            x = st.top();
            for(it = g[x].begin(); it != g[x].end(); it++){
                y = *it;
                if(v[y].c > v[y].f && lvldg[v[y].d] > lvldg[x]){
                    plusflow = min(plusflow, v[y].c - v[y].f);
                    st.push(v[y].d); stm.push(y); break;
                }
            }
            if(it == g[x].end()) break;
        }
        if(st.top() == N){
            while(!stm.empty()){
                y = stm.top(); stm.pop(); st.pop();
                v[y].f += plusflow;
                v[y].anti->f -= plusflow;
            }
            splusflow += plusflow;
        }
        else break;
    }
    return splusflow;
}

bool bfs(int N, int &plusflow)
{
    int lvldg[NMAX] = {0}, x, y;
    queue<int> q;
    q.push(1);lvldg[1] = 1;
    while(!q.empty()){
        x = q.front(); q.pop();
        for(it = g[x].begin(); it != g[x].end(); it++){
            y = *it;
            if(lvldg[v[y].d] == 0 && v[y].c > v[y].f) q.push(v[y].d),
                lvldg[v[y].d] = lvldg[x] + 1;
        }
    }
    if(lvldg[N] == 0) return false;
    plusflow = addflow(N, lvldg);
    return true;
}

int main()
{
    int n, m, x, y, c, maxflow = 0, plusflow;

    fin >> n >> m;
    for(int i = 1; i <= m; i++){
        fin >> x >> y >> c;
        v[i].c = c; v[i].d = y; v[i].anti = &v[m + i];
        v[m + i].d = x;
        g[x].push_back(i); g[y].push_back(m + i);
    }

    while(bfs(n, plusflow))
        maxflow += plusflow;

    fout << maxflow;

    return 0;
}