#include <bits/stdc++.h>

using namespace std;

ifstream f("maxflow.in");
ofstream g("maxflow.out");

int n,viz[1010],tata[1010],flux[1010][1010],c[1010][1010];
queue <int> q;
vector <int> v[1010];

void BF()
{
    for(int i=1;i<=n;i++)viz[i]=0;
    while(!q.empty())q.pop();

    q.push(1);
    viz[1]=1;
    while(!q.empty())
    {
        int nod=q.front();

        for(int i=0;i<v[nod].size();i++)
        {
            int vecin=v[nod][i];
            if(viz[vecin]==0 && flux[nod][vecin]<c[nod][vecin])
            {
                viz[vecin]=1;
                tata[vecin]=nod;
                q.push(vecin);
                if(vecin==n){return;}
            }
        }
        q.pop();
    }
}

int m,x,y,i,capacitate,dif,j,flux_min,FLUX_final;

int main()
{
    f>>n>>m;
    for(i=1;i<=m;i++)
    {
        f>>x>>y>>capacitate;

        v[x].push_back(y);
        c[x][y]=capacitate;

        v[y].push_back(x);
        /// c[y][x] = 0 daca nu exista arc y->x
    }

    for(i=1;i<=n;i++)
    {
        BF();
        flux_min=INT_MAX;
        int nod=n;

        /// cautam flux minim
        while(tata[nod]!=0)
        {
            int tata_nod=tata[nod];
            dif=c[tata_nod][nod]-flux[tata_nod][nod];
            flux_min=min(flux_min,dif);

            nod=tata[nod];
        }


        /// adaugam fluxul minim
        nod=n;
        while(tata[nod]!=0)
        {
            int tata_nod=tata[nod];
            flux[tata_nod][nod]+=flux_min;
            nod=tata[nod];
        }


        FLUX_final+=flux_min;
    }

    g<<FLUX_final;
    return 0;
}