#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <cstring>
using namespace std;

ifstream F("maxflow.in");
ofstream G("maxflow.out");

const int N = 1010;
const int M = 5010;

struct edge {
    int x,y,c[2];
    int _(int xx)
    {
        return x+y-xx;
    }
    int w(int xx,int yy)
    {
        return ( xx == x && yy == y ) ? 0 : 1;
    }
    int cap(int xx,int yy)
    {
        return w(xx,yy) == 0 ? c[0] : c[1];
    }
};

vector<int> v[N];
edge e[M];
int n,m,flow,dad[N],pl[N];

int go(int x)
{
    memset(dad,0,sizeof(dad));
    memset(pl,0,sizeof(pl));
    dad[1] = -1;

    queue<int> q;
    q.push( 1 );

    while ( !q.empty() )
    {
        int x = q.front();
        q.pop();

        for (int i=0;i<int(v[x].size());++i)
        {
            int idx = v[x][i];
            int y = e[idx]._(x);
            if ( dad[ y ] == 0 && e[idx].cap(x,y) > 0 )
            {
                dad[ y ] = x;
                pl[ y ] = idx;
                q.push( y );
            }
        }
    }

    return dad[n] != 0;
}

int main()
{
    F>>n>>m;
    for (int i=1,x,y,c;i<=m;++i)
    {
        F>>e[i].x>>e[i].y>>e[i].c[0];
        v[ e[i].x ].push_back( i );
        v[ e[i].y ].push_back( i );
    }
    //go(1); for (int i=1;i<=n;++i) cerr<<dad[i]<<' ';cerr<<'\n';
    //for (int i=1;i<=n;++i) cerr<<pl[i]<<' ';cerr<<'\n';
    while ( go(1) )
        for (int i=0;i<int(v[n].size());++i)
        {
            int idx = v[n][i];
            int x = e[idx]._(n);

            //cerr<<e[idx].cap(x,n) <<'\n';
            if ( dad[x] != 0 && e[idx].cap(x,n) > 0 )
            {
                int cap = e[idx].cap(x,n);
                for (int i=x;i!=1;i=dad[i])
                {
                    cap = min(cap,e[pl[i]].cap(dad[i],i));
                    if ( cap == 0 ) break;
                }
                if ( cap == 0 ) break;
                for (int i=x;i!=1;i=dad[i])
                {
                    int j = e[pl[i]].w(dad[i],i);
                   // cerr<<j<<'\n';
                    e[pl[i]].c[j] -= cap;
                    e[pl[i]].c[1-j] += cap;
                }
                int j = e[idx].w(x,n);
                e[idx].c[j] -= cap;

                flow += cap;
            }
        }
    G<<flow<<'\n';
}