#include <bits/stdc++.h>

using namespace std;

#define FILE_IO

typedef pair<int, int> pii;

int N, M, S, T, flow;
int cnt, v[2005], f[2005];
int cp[2005][2005];
vector <int> edg[2005];
queue <int> q;

void makeGoodEdges()
{
    vector <pii> badEdges;
    for(int i = 1; i <= N; i++)
        for(int j = i + 1; j <= N; j++)
        {
            if(!cp[i][j] && !cp[j][i])  continue;
            if(cp[i][j] && cp[j][i])
            {
                badEdges.push_back({i, j});
                continue;
            }
            edg[i].push_back(j);
            edg[j].push_back(i);
        }

    for(auto edge: badEdges)
    {
        int x = edge.first;
        int y = edge.second;
        N++;
        cp[y][N] = cp[N][x] = cp[y][x];
        cp[y][x] = 0;

        edg[x].push_back(y);
        edg[x].push_back(N);
        edg[y].push_back(N);
        edg[y].push_back(x);
        edg[N].push_back(x);
        edg[N].push_back(y);
    }
}

void push(int x, int y, int f)
{
    cp[x][y] -= f;
    cp[y][x] += f;
}

void BFS()
{
    ++cnt;
    v[S] = cnt;
    q.push(S);

    f[S] = 0;
    while(!q.empty())
    {
        int nod = q.front();
        q.pop();

        for(auto nxt: edg[nod])
            if(cp[nod][nxt] && v[nxt] != cnt && nxt != T)
            {
                f[nxt] = nod;
                v[nxt] = cnt;
                q.push(nxt);
            }
    }
}

int main()
{
    #ifdef FILE_IO
    freopen("maxflow.in", "r", stdin);
    freopen("maxflow.out", "w", stdout);
    #endif

    scanf("%d%d", &N, &M);
    S = 1; T = N;
    for(int i = 1; i <= M; i++)
    {
        int x, y, c;
        scanf("%d%d%d", &x, &y, &c);
        cp[x][y] += c;
    }
    makeGoodEdges();

    flow = 0;
    bool ok = 1;
    while(ok)
    {
        ok = 0;
        BFS();
        for(auto nxt: edg[T])
        {
            int fmax = cp[nxt][T];
            if(fmax == 0)   continue;
            for(int nod = nxt; nod != S; nod = f[nod])
                fmax = min(fmax, cp[ f[nod] ][nod]);
            if(fmax == 0)   continue;
            flow += fmax;
            push(nxt, T, fmax);
            for(int nod = nxt; nod != S; nod = f[nod])
                push(f[nod], nod, fmax);
            ok = 1;
        }
    }

    printf("%d\n", flow);
}