#include <bits/stdc++.h>
#define int long long

using namespace std;

const int NMAX=1000;
int capacity[NMAX+1][NMAX+1], flow[NMAX+1][NMAX+1];
int excess[NMAX+1], height[NMAX+1];
int n, m;

void push(int nod, int to)
{
    int d=min(excess[nod], capacity[nod][to]-flow[nod][to]);
    flow[nod][to]+=d;
    flow[to][nod]-=d;
    excess[nod]-=d;
    excess[to]+=d;
}

void relabel(int nod)
{
    int d=1e9;
    for(int i=1; i<=n; i++)
        if(capacity[nod][i]-flow[nod][i]>0)
            d=min(d, height[i]);
    if(d!=1e9)
        height[nod]=d+1;
}

vector<int> get_max_heights_nodes()
{
    int mx=0;
    for(int i=2; i<n; i++)
        if(excess[i]>0)
            mx=max(mx, height[i]);

    vector<int> rez;
    for(int i=2; i<n; i++)
        if(height[i]==mx && excess[i]>0)
            rez.push_back(i);
    return rez;
}

signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    freopen("maxflow.in", "r", stdin);
    freopen("maxflow.out", "w", stdout);
    cin>>n>>m;
    for(int i=1, u, v, cap; i<=m; i++)
    {
        cin>>u>>v>>cap;
        if(cap==0)continue;
        capacity[u][v]+=cap;
    }

    height[1]=n;
    excess[1]=1e9;
    for(int i=2; i<=n; i++)
        push(1, i);

    while(true)
    {
        vector<int> current = get_max_heights_nodes();
        if(current.empty())
            break;

        for(int &nod:current)
        {
            bool pushed=false;
            for(int i=1; i<=n && excess[nod]>0; i++)
                if(capacity[nod][i]-flow[nod][i]>0 && height[nod]==height[i]+1)
                {
                    push(nod, i);
                    pushed=true;
                }
            if(!pushed)
            {
                relabel(nod);
                break;
            }
        }
    }

    cout<<excess[n];
    return 0;
}