#include <stdio.h>
#include <vector>
#include <string.h>
#include <algorithm>
#include <cassert>
#include <ctime>
#include <cstdlib>
using namespace std;

#define pb push_back
#define FORIT( it, v ) for( typeof((v).begin()) it=(v).begin(); it!=(v).end(); ++it )
#define MaxN 1010
#define MaxM 10010

int i,n,m,x,y,z,maxflow;
int Father[MaxN];
vector <int> Vertex[MaxN];

struct edge
{
    int a,b,c,f;
    edge ()
    {
        a=b=c=f=0;
    }
    edge (int x,int y,int z)
    {
        a=x;
        b=y;
        c=z;
        f=0;
    }
    int length (int x)
    {
        if (x==b)
            return c-f;
        return c+f;
    }
    void increase (int x, int value )
    {
        if (x==b)
            f+=value;
        else
            f-=value;
    }
    int other (int node)
    {
        return a+b-node;
    }
    void print()
    {
        printf ("%ld %ld %ld %ld\n",a,b,c,f);
    }
}Edge[MaxM];
int Queue[MaxN];
int BFS()
{
    int node,left,right,next,last,value;
    edge ed1,ed2;
    left=1;
    right=1;
    Queue[1]=1;
    //Put first node into queue;
    while ( left <= right )
    {
        node=Queue[left++];
        if (node==n)
            continue;
        FORIT (it,Vertex[node])
        {
            ed1=Edge[*it];
            next=ed1.other(node);
            //pull the other node from curentWe found a path from source to sink edge
            if (!Father[next] && ed1.length(next)>0 )
            {
                Father[next]=*it;
                Queue[++right]=next;
            }
        };
    }
    bool ok=0;
    FORIT (it,Vertex[n])
    {
        ed1=Edge[*it];
        last=ed1.other(n);
        //pull the other node from curent edge
        if (Father[last])
        {
            // We found a path from source to sink
            value=ed1.length(n);
            if ( value > 0 )
            {
                //We go back to the source
                node = last;
                while ( node!=1)
                {
                    ed1 = Edge[Father[node]];
                    last = ed1.other(node);
                    value = min (value , ed1.length(node));
                    node = last;
                }
                node = Edge[*it].other(n);
                if (value > 0)
                {
                    ok=1;
                    Edge[*it].increase(n,value);
                    while (node !=1)
                    {
                        last=Edge[Father[node]].other(node);
                        Edge[Father[node]].increase(node,value);
                        node = last;
                    }
                    maxflow+=value;
                }

            }
        }
    };
    return ok;
}
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",&x,&y,&z);
        Edge[i] = edge(x,y,z);
        Vertex[x].pb(i);
        Vertex[y].pb(i);
    }
    Father[1]=1;
    while ( BFS() )
        memset(Father,0,sizeof Father),Father[1]=1;
    printf ("%d\n",maxflow);
    //for (i=1;i<=m;i++)
        //Edge[i].print();

    return 0;
}