#include <stdio.h>


int d[1000], os[1000];
long rez[1000][1000];
int n,m;
long FLUX;


void Olvas()
{
    int a, b;
    long c;

    freopen("maxflow.in", "r", stdin);
    scanf("%d %d", &n, &m);
    for (int i = 1; i<=m; i++)
    {
        scanf("%d %d %ld", &a,&b,&c);
        rez[a][b] = c;
    }
}

int Vanut(int x)
{
    int i;
    for (i = 1; ((i<=n) && !((d[i] == d[x] - 1) && (rez[x][i]))); ++i);
    return (i<=n)?(i):(0);
}

void Lep(int *x, int y, long *min)
{
    os[y] = *x;
    *min = (*min > rez[*x][y])?(rez[*x][y]):(*min);
    *x = y;
}

void Novel(long min)
{
    int x = n;
    while (x!=1)
    {
        rez[os[x]][x] -= min;
        rez[x][os[x]] += min;
        x = os[x];
    }
}


void Vissza(int *x)
{
    long min = n;
    for (int i=1;i<=n;i++)
    {
        if (rez[*x][i] && d[i]<min)
            min = d[i];
    }
    d[*x] = (min==n)?(min):(min+1);
    *x = (*x==1)?(*x):(os[*x]);
}


void Fluxamol()
{
    for (int i=1;i<=n;i++)
        FLUX += rez[i][1];
}


void Bejar()
{
    int sor[100000];
    int y;
    int e = 1, v = 1;
    int i;
    sor[e] = n;

    while (e<=n)
    {
        y = sor[e];
        for (i=1;i<=n;i++)
        {
            if (rez[i][y] && (d[y] + 1 < d[i] || d[i] == 0))
            {
                d[i] = d[y] + 1;
                sor[++v] = i;
            }
        }
        ++e;
    }
}

void Megold()
{
    Bejar();
    int x = 1;
    int y;
    long min = 2000000000;
    while (d[1]<n)
    {
        if (y = Vanut(x))
        {
            Lep(&x,y,&min);
            if (x == n)
            {
                Novel(min);
                x = 1;
                min = 2000000000;
            }
        }
        else
        {
            Vissza(&x);
        }
    }
    Fluxamol();
}


void Kiir()
{
    freopen("maxflow.out", "w", stdout);
    printf("%ld", FLUX);
}

int main()
{
    Olvas();
    Megold();
    Kiir();
    return 0;
}