#include <iostream>
#include <fstream>
#include <vector>
#include <queue>

using namespace std;

ifstream in("maxflow.in");
ofstream out("maxflow.out");
int n, m, ok, ans;
vector<pair<int, int>> v[1005];
pair<int, int> lat[10005];
pair<int, int> viz[5005];
int INF = (1 << 30);

void bfs()
{
    viz[1] = {-1, -1};
    queue<int> q;
    q.push(1);

    while(!q.empty())
    {
        int nod = q.front();
        q.pop();

        if(nod == n)
        {
            break;
        }

        for(auto it: v[nod])
        {
            if(viz[it.first].first == 0 && lat[it.second].second - lat[it.second].first > 0)
            {
                viz[it.first] = {nod, it.second};
                q.push(it.first);
            }
        }
    }

    if(viz[n].first == 0)
    {
        return;
    }

    ok = 1;
    int nod = n;
    int flux = INF;

    while(viz[nod].first != -1)
    {
        flux = min(flux, lat[viz[nod].second].second - lat[viz[nod].second].first);

        nod = viz[nod].first;
    }

    ans += flux;

    nod = n;
    while(viz[nod].first != -1)
    {
        if(viz[nod].second <= m)
        {
            lat[viz[nod].second].first += flux;
            lat[viz[nod].second + m].first -= flux;
        }
        else
        {
            lat[viz[nod].second].first += flux;
            lat[viz[nod].second - m].first -= flux;
        }

        nod = viz[nod].first;
    }

}

signed main()
{
    in>>n>>m;

    int x, y, z;
    for(int i = 1; i<=m; i++)
    {
        in>>x>>y>>z;

        v[x].push_back({y, i});
        lat[i] = {0, z};

        v[y].push_back({x, i + m});
        lat[i + m] = {0, 0};
    }

    ok = 1;
    while(ok == 1)
    {
        ok = 0;

        for(int i = 1; i<=n; i++)
        {
            viz[i] = {0, 0};
        }

        bfs();
    }

    out<<ans;

    return 0;
}