#include <bits/stdc++.h>

using namespace std;
ifstream fin("maxflow.in");
ofstream fout("maxflow.out");

int c[1003][1003], f[1003][1003];
int tata[1003];
int v[1003];
int n,s,d,m;

bool bfs(vector<int> arce_directe[],vector<int> arce_inverse[] )
{

    for(int i=1; i<=n; i++)
    {
        tata[i]=0;
        v[i]=0;
    }
    queue<int> q;
    q.push(s);
    v[s]=1;

    while(q.empty()==false)
    {
        int i = q.front();
        q.pop();
        for(auto j : arce_directe[i])
        {
            if(v[j]==0&&c[i][j]-f[i][j]>0)
            {
                q.push(j);
                tata[j] = i;
                v[j] = 1;
                if(j==d)
                    return true;
            }
        }

        for(auto j : arce_inverse[i])
        {
            if(v[j]==0&&f[j][i]>0)
            {
                q.push(j);
                tata[j] = -i;
                v[j] = 1;
                if(j==d)
                    return true;
            }
        }

    }
    return false;
}


int main()
{

    fin>>n>>m;
    vector<int> arce_directe[n+1];
    vector<int> arce_inverse[n+1];
    for(int i=1; i<=m; i++)
    {
        int a1,b1,c1;

        fin>>a1>>b1>>c1;
        arce_directe[a1].push_back(b1);
        arce_inverse[b1].push_back(a1);
        c[a1][b1]=c1;
        f[a1][b1]=0;

    }
    s=1;
    d=n;
    long long flux=0;

    while(bfs(arce_directe,arce_inverse)==true)
    {
        for(auto nod : arce_inverse[d])
            if(f[nod][d] != c[nod][d] && v[nod])
            {
                tata[d]=nod;
                int flux_lant=INT_MAX;
                int i=d;
                while(i!=s)
                {

                    int j=tata[i];

                    if(j<0)
                    {
                        j=-j;
                        flux_lant=min(flux_lant, f[i][j]);
                    }
                    else
                    {
                        flux_lant=min(flux_lant, c[j][i]-f[j][i]);
                    }

                    i=tata[i];
                    if(i<0)
                        i=-i;

                }

                i=d;
                while(i!=s)
                {

                    int j=tata[i];
                    if(j<0)
                    {
                        j=-j;
                        f[i][j]-=flux_lant;
                    }
                    else
                        f[j][i]+=flux_lant;

                    i=tata[i];
                    if(i<0)
                        i=-i;

                }

                flux+=flux_lant;
            }
    }

    fout<<flux<<"\n";

    return 0;
}