#include <bits/stdc++.h>

using namespace std;

#define FILE_IO

typedef pair<int, int> pii;

class flowNetwork
{
private:
    int N, S, T;
    vector <int> h, e, inq, cnt;
    vector < vector<int> > cp, edg;
    queue <int> q;

    void makeGoodEdges(int unused)
    {
        vector <pii> badEdges;
        for(int i = 1; i <= N; i++)
            edg[i].clear();

        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 pushInQ(int nod)
    {
        if(!inq[nod] && e[nod])
        {
            inq[nod] = 1;
            q.push(nod);
        }
    }

    void push(int x, int y)
    {
        if(h[x] != h[y] + 1)    return;
        if(!e[x])   return;
        if(!cp[x][y])   return;

        int add = min(e[x], cp[x][y]);
        e[x] -= add;
        e[y] += add;
        cp[x][y] -= add;
        cp[y][x] += add;
        pushInQ(y);
    }

    void gap(int hh)
    {
        for(int i = 1; i <= N; i++)
        {
            if(i == S || i == T)    continue;
            if(h[i] < hh)   continue;
            cnt[ h[i] ]--;
            h[i] = max(h[i], N + 1);
            cnt[ h[i] ]++;
            pushInQ(i);
        }
    }

    void relabel(int nod)
    {
        cnt[ h[nod] ]--;
        int hmin = 2 * N;
        for(auto nxt: edg[nod])
            if(cp[nod][nxt])
                hmin = min(hmin, h[nxt]);
        h[nod] = hmin + 1;
        cnt[ h[nod] ]++;
        pushInQ(nod);
    }

    void discharge(int nod)
    {
        for(auto nxt: edg[nod])
            push(nod, nxt);
        if(e[nod])
        {
            if(cnt[ h[nod] ] == 1)
                gap(h[nod]);
            else
                relabel(nod);
        }
    }

    int getMaxFlow()
    {
        inq[S] = inq[T] = 1;
        h[S] = 1;
        for(auto nxt: edg[S])
        {
            e[S] += cp[S][nxt];
            push(S, nxt);
        }
        h[S] = N;
        cnt[0] = N - 1;
        cnt[N] = 1;

        while(!q.empty())
        {
            int nod = q.front();
            q.pop();
            inq[nod] = 0;
            discharge(nod);
        }

        return e[T];
    }

public:
    void init(int _N)
    {
        N = _N;
        int NN = 2 * (N + 5);
        h.resize(NN);
        e.resize(NN);
        inq.resize(NN);
        cnt.resize(NN);
        cp.resize(NN);
        edg.resize(NN);
        for(int i = 0; i < NN; i++)
            cp[i].resize(NN);
    }

    void addEdge(int x, int y, int c)
    {
        cp[x][y] += c;
    }

    void makeGoodEdges()
    {
        makeGoodEdges(1);
    }

    int getMaxFlow(int _S, int _T)
    {
        S = _S;
        T = _T;
        return getMaxFlow();
    }
}flow;

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

    int N, M;
    scanf("%d%d", &N, &M);
    flow.init(N);
    for(int i = 1; i <= M; i++)
    {
        int x, y, c;
        scanf("%d%d%d", &x, &y, &c);
        flow.addEdge(x, y, c);
    }
    flow.makeGoodEdges();

    int ans = flow.getMaxFlow(1, N);

    printf("%d\n", ans);

    return 0;
}