#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 s, d, c, f;
} v[MMAX];

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

int blockFlow_ed_ka(int n, int m, int lvlg[])
{
    int x, y, i, flow = 0;
    do{
        muchie e;
        queue<int> q;
        int pred[NMAX] = {0};

        q.push(1);
        while(!q.empty()){
            x = q.front(); q.pop();
            for(it = g[x].begin(); it != g[x].end(); it++){
                e = v[*it];
                if(e.d != 1 && e.c > e.f && lvlg[e.d] > lvlg[x]){
                    pred[e.d] = *it;
                    q.push(e.d);
                }
            }
        }
        if(pred[n] != 0){
            int plusflow = inf;
            for(i = pred[n]; i != 0; i = pred[v[i].s])
                plusflow = min(plusflow, v[i].c - v[i].f);

            for(i = pred[n]; i != 0; i = pred[v[i].s])
                v[i].f += plusflow, v[m + i].f -= plusflow;
            flow = flow + plusflow;
        }
        else break;
    }while(1);

    return flow;
}

bool bfs(int n, int m, int &plusflow)
{
    int i, x, y, lvlg[NMAX] = {0};
    lvlg[1] = 1;
    queue<int> q; q.push(1);

    while(!q.empty()){
        x = q.front(); q.pop();
        for(it = g[x].begin(); it != g[x].end(); it++){
            y = *it;
            if(lvlg[v[y].d] == 0 && v[y].c > v[y].f)
                q.push(v[y].d), lvlg[v[y].d] = lvlg[x] + 1;
        }
    }
    if(lvlg[n] == 0) return false;
    plusflow = blockFlow_ed_ka(n, m, lvlg);
    return true;
}

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

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

    while(bfs(n, m, plusflow))
        flow += plusflow;

    fout << flow;

    return 0;
}