#include <fstream>
#include <cstring>
#include <queue>

#define grafSize 1001
#define TSize 1001

#define fWidth 1001
#define fHeight 1001
#define costWidth 1001
#define costHeight 1001

#define INF 0x7fffffff

using namespace std;

ifstream in;
ofstream out;

struct gn
{
    int nod;
    gn *link;
}*graf[grafSize];

int cost[costHeight][costWidth];
int f[fHeight][fWidth];

int T[TSize];

int Source,Sink;

inline void addedge(int x,int y)
{
    gn *p;

    p=new gn;
    p->nod=y;
    p->link=graf[x];
    graf[x]=p;
}

inline int BFS()
{
    queue <int> q;
    int ok=0;

    memset(T,-1,sizeof(T));
    T[Source]=0;
    q.push(Source);

    for(int nod;!q.empty();q.pop())
    {
        nod=q.front();

        for(gn *p=graf[nod];p;p=p->link)
            if(T[p->nod]==-1&&cost[nod][p->nod]>f[nod][p->nod])
            {
                if(p->nod!=Sink)
                {
                    q.push(p->nod);
                    T[p->nod]=nod;
                }
                else ok=1;
            }
    }

    return ok;
}

inline int MaxFlow()
{
    int flux=0;
    int min;

    for(int drum=BFS();drum;drum=BFS())
        for(gn *p=graf[Sink];p;p=p->link)
        {
            T[Sink]=p->nod;
            min=INF;

            for(int nod=Sink;nod!=Source;nod=T[nod])
                if(min>cost[T[nod]][nod]-f[T[nod]][nod])
                    min=cost[T[nod]][nod]-f[T[nod]][nod];

            if(!min) continue;

            for(int nod=Sink;nod!=Source;nod=T[nod])
            {
                f[T[nod]][nod]+=min;
                f[nod][T[nod]]-=min;
            }

            flux+=min;
        }

    return flux;
}

int main()
{
    int M,N,x,y,z;

    memset(f,0,sizeof(f));
    memset(cost,0,sizeof(cost));

    in.open("maxflow.in");

    in>>N>>M;
    for(;M--;)
    {
        in>>x>>y>>z;

        cost[x][y]+=z;
        cost[y][x]=-cost[x][y];

        addedge(x,y);
        addedge(y,x);
    }

    in.close();

    Source=1;
    Sink=N;

    out.open("maxflow.out");

    out<<MaxFlow()<<'\n';

    out.close();

    return 0;
}