#include <cstdio>

using namespace std;

const int MAX_N = 1000, MAX_M = MAX_N*MAX_N;

FILE *in, *out;

int lst[MAX_N+1], urm[MAX_M+1], vf[MAX_M+1], c[MAX_M+1];
int nrg;
int f[MAX_N+1][MAX_N+1];


int n,m;

int h[MAX_N+1], e[MAX_N+1];

int cate[2*MAX_N];

int minim(int a, int b)
{
    return (a<b)?a:b;
}

int maxim(int a, int b)
{
    return (a>b)?a:b;
}

void add(int x, int y, int z)
{
    nrg++;
    urm[nrg] = lst[x];
    vf[nrg] = y;
    c[nrg] = z;
    lst[x] = nrg;
}

struct Nod {
    Nod* next;
    int val;
};

struct lista {
    Nod* head;
};

lista* l;

void push(int u, int p)
{
    int val = minim(e[u], c[p]-f[u][vf[p]]);
    f[u][vf[p]] += val;
    f[vf[p]][u] -= val;
    e[u] -= val;
    e[vf[p]] += val;
}

void initpreflow()
{
    cate[0] = n-1;
    cate[n] = 1;
    h[1] = n;
    int p = lst[1];
    while(p != 0)
    {
        e[1] += c[p];
        push(1,p);
        p = urm[p];
    }
}


void relabel(int u)
{
    cate[h[u]]--;
    h[u] = 2*n;
    int p = lst[u];
    while(p != 0)
    {
        if(c[p]-f[u][vf[p]] > 0)
            h[u] = minim(h[u], h[vf[p]]+1);
        p = urm[p];
    }
    cate[h[u]]++;
}

void gap(int k)
{
    for(int i = 1; i < n; i++)
        if(h[i] >= k && h[i] < n)
        {
            cate[h[i]]--;
            h[i] = n+1;
            cate[h[i]]++;
        }
}

void discharge(int u)
{
    int p = lst[u];
    int v;
    while(p != 0)
    {
        v = vf[p];
        if(e[u] > 0)
            if(c[p]-f[u][v] > 0 && h[u] == h[v]+1)
                push(u,p);
        p = urm[p];
    }
    if(e[u] > 0)
        if(cate[h[u]] == 1)
            gap(h[u]);
    else relabel(u);
    /*while(e[u] > 0)
    {
        int v = vf[p];
        if(p == 0)
        {
            if(cate[h[u]] == 1)
                gap(h[u]);
            else
                relabel(u);
            p = lst[u];
        } else if(c[p]-f[u][v] > 0 && h[u] == h[v]+1)
            push(u,p);
        else
            p = urm[p];
    }*/
}

int main()
{
    in = fopen("maxflow.in", "r");
    out = fopen("maxflow.out", "w");
    fscanf(in, "%d%d", &n, &m);
    int cost;
    int z, y;
    for(int i = 1; i <= m; i++)
    {
        fscanf(in, "%d%d%d", &z, &y, &cost);
        add(z, y, cost);
    }
    initpreflow();
    l = new lista;
    l->head = new Nod;
    Nod* x = l->head;
    Nod* oldNod = l->head;
    for(int i = 2; i < n; i++)
    {
        x->val = i;
        x->next = new Nod;
        x = x->next;
    }
    x = l->head;
    while(x != NULL)
    {
        int oldh = h[x->val];
        discharge(x->val);
        if(h[x->val] > oldh && h[x->val] != 2*n)
        {
            if(x != l->head && oldNod != l->head)
            {
                oldNod->next = oldNod->next->next;
                x->next = l->head;
                l->head = x;
            }
            x = l->head;
        } else {
            oldNod = x;
            x = x->next;
        }
    }
    int sol = 0;
    int p = lst[1];
    while(p != 0)
    {
        if(h[vf[p]] == 2*n)
            sol -= f[1][vf[p]];
        sol += f[1][vf[p]];
        p = urm[p];
    }
    fprintf(out, "%d", sol);
    fclose(in);
    fclose(out);
    return 0;
}