#include <bits/stdc++.h>

using namespace std;

vector <int> id[1005];

vector <int> v[1005];

int l[5005];

int r[5005],mc[5005];

int n;

int cnt;

int f[1005];

int mn;

bool da;

int el;

void dfs(int k,int pt,int mx,int in)
{
    r[in]=k;
    mc[in]=mx;
    f[k]=cnt;
    if(k==n || da==true)
    {
        el=in;
        da=true;
        return;
    }
    for(int h=0;h<v[k].size();++h)
    {
        int a=v[k][h];
        if(f[a]!=cnt && l[id[k][h]]!=0)
        {
            dfs(a,k,id[k][h],in+1);
            if(k==n || da==true)
            {
                da=true;
                return;
            }
        }
    }
    f[k]=cnt-1;
}

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;
        dfs(1,0,0,1);
        if(da==true)
        {
            ok=true;
            mn=INT_MAX;
            for(int i=2;i<=el;++i)
            {
                if(l[mc[i]]<mn)
                {
                    mn=l[mc[i]];
                }
            }
            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;
}