#include <iostream>
#include <fstream>

using namespace std;

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

struct graf{
int nod;
graf* next;
};

int n;

graf* g[1001];
int res[1001][1001];

int flow;
int c[1001];
int q[1001];
int a,b;
int tati[1001];

int vecini[1001];
int len = 1;

void add(int a, int b, graf* v[])
{
    graf* q = new graf;
    q->nod  = b;
    q->next = v[a];
    v[a] = q;
}

void BFS(int k){
    graf*  p;
    for(p = g[k]; p!=NULL; p=p->next){
        if(c[p->nod] == 0 && res[k][p->nod] > 0){
            ++b;
            q[b] = p->nod;
            c[p->nod] = 1;
            tati[p->nod] = k;
        }
    }
    ++a;

    if(b >= a)
        BFS(q[a]);
}

void findPath(int k, int minim){
    int x = k;

    while(x != 1){
        if(minim > res[tati[x]][x])
            minim = res[tati[x]][x];
        x = tati[x];
    }
    flow = flow + minim;

    x = k;
    while(x != 1){
        res[tati[x]][x] = res[tati[x]][x] - minim;
        res[x][tati[x]] = res[x][tati[x]] + minim;
        x = tati[x];
    }
}

void init(){
    int i;
    c[1] = 1;
    for(i=2;i<=n - 1;++i)
        c[i] = 0;
    a = b = 0;
    q[0] = 1;
}


void update(){
    int i;
    bool s = 0;
    init();
    BFS(1);
    for(i=1;i<=len;++i)
        if(c[vecini[i]] == 1 && res[vecini[i]][n] > 0)
            s = 1;

    if(!s)
        return;

    for(i=1;i<=len;++i){
            if(c[vecini[i]] == 1 && res[vecini[i]][n] > 0)
                findPath(vecini[i],res[vecini[i]][n]);
    }
    update();
}


int main()
{
    int m,x,y,z,i,j;
    fin >> n >> m;
    for(i=1;i<=m;++i){
        fin >> x >> y >> z;
        res[x][y] = z;

        if(y == n)
            vecini[len] = x,
            ++len;

        if(y != n){
            add(x,y,g);
            add(y,x,g);
        }
    }
    update();

    cout << flow;


    return 0;
}