#include <iostream>
#include <fstream>
#include <stdio.h>
#include <string.h>
#define MAX_N 1000
#define MAX_M 5000
#define INF 2000000000
using namespace std;
struct nod
{
    int nr,cost;
    nod *next;
}*First[MAX_N+5];
int N,M;
int Cap[MAX_N+5][MAX_N+5],T[MAX_N+5];
void Insert(int x,int y,int cost)
{
    nod *q=new nod;
    q->nr=y;
    q->cost=cost;
    q->next=First[x];
    First[x]=q;
}
void Read()
{
    ifstream fin("maxflow.in");
    fin>>N>>M;
    int i,x,y,cost;
    for(i=1;i<=M;i++)
    {
        fin>>x>>y>>cost;
        //if(x==y)
//             continue;
        Insert(x,y,cost);
        Cap[x][y]=cost;
    }
}
int Road()
{
    int c[MAX_N+5],i,cur,p=1,u=1;
    c[p]=1;
    T[1]=0;
    nod *q;
    while(p<=u)
    {
        cur=c[p];
        for(q=First[cur];q;q=q->next)
        {
            i=q->nr;
            if(Cap[cur][i]>0&&T[i]==0)
            {
                u++;
                c[u]=i;
                T[i]=cur;
                if(i==N)
                    return 1;
            }
        }
        p++;
    }

    return 0;
}
void write_road(int k)
{
//    printf(" / t[%d]=%d -> ",k,T[k]);
    if(T[k]==0){
        printf("1 ");
        return;
    }
    write_road(T[k]);
    printf("%d ",k);
}
void Solve(int k,int &min)
{
    if(T[k]>0)
    {
        if(Cap[T[k]][k]>0&&min>Cap[T[k]][k])
            min=Cap[T[k]][k];
        Solve(T[k],min);
        Cap[T[k]][k]-=min;
    }
}
int ReturnFlux()
{
    nod *q;
    int s=0;
    for(q=First[1];q;q=q->next)
    {
        s+=q->cost-Cap[1][q->nr];
    }
    return s;
}
int main()
{
    Read();
    int sw=Road(),min=INF;

    while(sw)
    {
//        write_road(N);
//        printf("\n");
        min=INF;
//        printf("1\n");
        Solve(N,min);
//        printf("2\n");
        memset(T,0,sizeof(T));
        sw=Road();
//        printf("3:%d\n",sw);
    }
    freopen("maxflow.out","w",stdout);
    printf("%d\n",ReturnFlux());
    fclose(stdout);
    return 0;
}