#include <iostream>
#include <fstream>

using namespace std;

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

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

int n;
int lol;

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

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

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,int d){
    graf*  p;
    ++numbs[d];
    for(p = g[k]; p!=NULL; p=p->next){
        if(c[p->nod] == 0 && res[p->nod][k] > 0){
            ++b;
            q[b] = p->nod;
            c[p->nod] = 1;
            dist[p->nod] = d + 1;
        }
    }
    ++a;

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

void augment(int k){
    int x = k;
    int minim = 100200;

    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];
    }
}





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

    c[n] = 1;
    for(i=1;i<=n-1;++i)
        c[i] = 0;
    a = b = 0;
    q[0] = n;

    BFS(n,0);
    int current = 1;
    int aux;
    bool liar = 1;

    while(dist[1] < n){
            graf*  p;
            aux = 1002;
            liar = 1;
            for(p = g[current]; p!=NULL; p=p->next){
                if(dist[p->nod]<aux && res[current][p->nod])
                    aux = dist[p->nod];

                if(dist[p->nod] + 1 == dist[current] && res[current][p->nod]){
                    liar = 0;
                    tati[p->nod] = current;
                    current = p->nod;
                    if(current == n){
                        augment(n);
                        current = 1;
                    }
                    break;
                }
            }

            if(liar){
                --numbs[dist[current]];
                if(numbs[dist[current]] == 0)
                    {
                        ++lol;
                        if(lol > 100)
                            break;
                    }
                dist[current] = aux + 1;
                ++numbs[aux + 1];


                if(current != 1)
                    current = tati[current];
            }
    }


    fout << flow;


    return 0;
}