#include <cstdio>
#include <vector>
using namespace std;
#define pb push_back
#define INF 0x3f3f3f3f
#define maxn 5005

typedef struct { long T[maxn]; } stiva;
typedef struct { long a,b,c; } muchie;
typedef struct { long e,vf; } bf;

bf BFs[maxn];
muchie T[maxn];
stiva gol,viz,last;

vector <long> Mu[1005];
vector <long> :: iterator it;
long act,rez;
long n,m,a,b,c,i,j;
long prim,ultim;
long F[maxn];

bool bfs ( )
{
    prim=ultim=1;

    viz=gol;
    last=gol;

    BFs[1].e=INF;
    BFs[1].vf=1;
    viz.T[1]=1;

    long mu;
    //printf ("\n");
    while ( prim <= ultim )
    {
        //printf ("%d %d %d\n", BFs[prim].vf, prim, ultim );
        for ( it =  Mu [BFs[prim].vf] . begin (); it!= Mu[ BFs[prim].vf ] . end () && prim <= ultim; it++ )
        {
            mu=*it;
            //printf ("  %d %d %d\n", T[mu].a,T[mu].b,T[mu].c );
            if ( mu > 0 )
            {
                if ( ( F[mu] != T[mu].c ) && ( !viz.T[ T[mu].b ] ) )
                {
                    viz.T[ T[mu].b ]=1;
                    last.T[ T[mu].b ] = mu;
                    ultim++;
                    BFs[ultim]. vf = T[mu].b;
                    BFs[ultim]. e = min ( BFs[prim].e , T[mu].c - F[mu] ) ;

                    if ( T[mu].b == n )
                    {

                        prim=ultim+10;
                        break;
                    }
                }
            }
            else{
                mu*=-1;
                if ( ( F[mu] !=0 ) && ( !viz.T[ T[mu].a ] ) )
                {
                    viz.T[ T[mu].a ]=1;
                    last.T[ T[mu].a ] = -mu;
                    ultim++;
                    BFs[ultim]. vf = T[mu].a;
                    BFs[ultim]. e = min ( BFs[prim].e , T[mu].c ) ;
                    if ( T[mu].a == n )
                    {

                        prim=ultim+10;
                        break;
                    }
                }
            }
        }
        prim++;
    }

    // reproducem drumul
    if ( BFs[ultim].vf == n )
    {
        /*for ( j=1; j<=n; j++ )
            printf ("      %d\n",last.T[j]);*/
        act=n;
        while ( act!=0 )
        {
            if ( last.T[act] > 0 )
            {
                // drumul s-a parcurs de la a-b
                F[ last.T[act] ]+= BFs[ultim].e;
                act= T [ last.T[ act ] ].a;
            }
            else{
                // drumul s-a parcurs de la b-a
                F[ -last.T[act] ]+= BFs[ultim].e;
                act= T [ -last.T[ act ] ].b;
            }
        }
        /*for ( j=1; j<=m; j++ )
            printf ( "%d) F:%d  - c:%d - a:%d b:%d\n",j,F[j],T[j].c,T[j].a,T[j].b);
        printf ("\n");*/
        return 1;
    }
    return 0;
}

int main()
{
    freopen ( "maxflow.in", "r", stdin );
    freopen ( "maxflow.out", "w", stdout );
    scanf ( "%d %d", &n, &m );
    for ( i=1; i<=m; i++ )
    {
        scanf ( "%d %d %d", &a, &b, &c );
        T[i].a=a;
        T[i].b=b;
        T[i].c=c;
        Mu[a].pb(i);
        Mu[b].pb(-i);
    }
    while ( bfs () )
        ;
    for ( it=Mu[n].begin (); it!=Mu[n].end (); it++ )
    {
        act=*it;
        rez+=F[ -act ];
    }
    printf ("%d", rez);
    return 0;
}