#include <fstream>
#include <vector>
#include <queue>
using namespace std;
int n,m,i,x,y,z,ok,maxi,cap[1005],tt[1005],w[1005][1005],r[1005][1005];
vector <int> f[1005],b[1005];
queue <int> q;
int main()
{
    ifstream cin("maxflow.in");
    ofstream cout("maxflow.out");
    cin>>n>>m;
    for(i=1; i<=n; i++)
    {
        f[i].push_back(0);
        b[i].push_back(0);
    }
    for(i=1; i<=m; i++)
    {
        cin>>x>>y>>z;
        f[x][0]++;
        f[x].push_back(y);
        b[y][0]++;
        b[y].push_back(x);
        w[x][y]=z;
        maxi=max(maxi,z);
    }
    ok=1;
    while(ok)
    {
        ok=0;
        for(i=1; i<=n; i++) cap[i]=0;
        for(i=1; i<=n; i++) tt[i]=0;
        cap[1]=maxi;
        q.push(1);
        while(!q.empty())
        {
            x=q.front();
            q.pop();
            for(i=1; i<=f[x][0]; i++)
            {
                y=f[x][i];
                z=min(cap[x],w[x][y]-r[x][y]);
                if(z>cap[y])
                {
                    cap[y]=z;
                    q.push(y);
                    tt[y]=x;
                }
            }
            for(i=1; i<=b[x][0]; i++)
            {
                y=b[x][i];
                z=min(cap[x],r[y][x]);
                if(z>cap[y])
                {
                    cap[y]=z;
                    q.push(y);
                    tt[y]=-x;
                }
            }
        }
        if(cap[n])
        {
            ok=1;
            x=n;
            while(x!=1)
            {
                y=tt[x];
                if(y>0)
                {
                    r[y][x]+=cap[n];
                }
                else
                {
                    y*=-1;
                    r[x][y]-=cap[n];
                }
                x=y;
            }
        }
    }
    x=0;
    for(i=1; i<n; i++) x+=r[i][n];
    cout<<x;
    return 0;
}