#include <bits/stdc++.h>

using namespace std;

vector <int> id[1005];

vector <int> v[1005];

int l[10005];

int r[5005],mc[5005];

int rr[5005],mcc[5005],ix[5005];

int n;

int cnt;

int f[1005];

int mn;

bool da;

int el;



int main()
{
    ifstream cin("maxflow.in");
    ofstream cout("maxflow.out");
    int m,x,y,z;
    cin>>n>>m;
    for(int i=1;i<=m;++i)
    {
        cin>>x>>y>>z;
        v[x].push_back(y);
        id[x].push_back(i);
        v[y].push_back(x);
        id[y].push_back(i+m);
        l[i]=z;
    }
    bool ok=true;
    long long cx=0;
    while(ok==true)
    {
        ++cnt;
        ok=false;
        da=false;
        deque <int> q,qi;
        q.push_back(1);
        qi.push_back(1);
        f[1]=cnt;
        while(q.size())
        {
            if(f[n]!=cnt)
            {


            for(int h=0;h<v[q.front()].size();++h)
            {
                if(l[id[q.front()][h]]!=0 && f[v[q.front()][h]]!=cnt)
                {
                    rr[v[q.front()][h]]=q.front();
                    mcc[v[q.front()][h]]=id[q.front()][h];
                    ix[v[q.front()][h]]=qi.front()+1;
                    f[v[q.front()][h]]=cnt;
                    q.push_back(v[q.front()][h]);
                    qi.push_back(qi.front()+1);
                }
            }
            }
            else
            {
                break;
            }
            q.pop_front();
            qi.pop_front();
        }
        if(f[n]==cnt)
        {
            da=true;
        }
        if(da==true)
        {
            int nod=n;
            el=ix[n];
            mn=INT_MAX;
            for(int i=ix[n];i>=1;--i)
            {
                r[i]=nod;
                mc[i]=mcc[nod];
                nod=rr[nod];
                if(i>=2 && l[mc[i]]<mn)
                {
                    mn=l[mc[i]];
                }
            }
            ok=true;


            for(int i=2;i<=el;++i)
            {
                l[mc[i]]-=mn;
                if(mc[i]>m)
                {
                    l[mc[i]-m]+=mn;
                }
                else
                {
                    l[mc[i]+m]+=mn;
                }
            }
            cx+=mn;
        }
    }
    cout<<cx;
    return 0;
}