#include <stdio.h>
#include <queue>
using namespace std;
int n,m,i,C[1001][1001],R[1001][1001],flux,last,d[1001],v[1001],t,now;
queue<int> Q;
// C - capacitatile muchiilor
// R - subgraful obtinut la pasul 1 al alg.
void citire()
{
    int i,x,y,z;
    scanf("%i%i",&n,&m);
    for (i=1;i<=m;i++)
    {
        scanf("%i%i%i",&x,&y,&z);
        C[x][y]=z;
        if (x==1)
        {
            last+=z; //maximul de flux pe care il pot baga
            v[++t]=y; //vecinii sursei
        }
    }
}
int DFS(int s,int cap)
{
    if (cap==0) return 0;
    if (s==n) return cap;

    int i,x,flux=0;
    for (i=1;i<=R[s][0];i++)
    {
        x=R[s][i];
        if (C[s][x]==0) continue;

        int r=DFS(x,min(cap-flux,C[s][x]));
        if (r)
        {
            C[s][x]-=r;
            C[x][s]+=r;
            flux+=r;
        }
    }
    return flux;
}
int dinic()
{
    int i,flux=0,s;
    for (i=1;i<=n;i++) d[i]=-1,R[i][0]=0;
    Q.push(1); d[1]=0;

    while (!Q.empty()) //BFS
    {
        s=Q.front();
        Q.pop();

        //if (s==n) break;

        for (i=1;i<=n;i++)
        {
            if (C[s][i]==0) continue;
            if (d[i]==-1)
            {
                d[i]=d[s]+1;
                Q.push(i);
                R[s][++R[s][0]]=i;
            }
            else if (d[i]==d[s]+1)
                R[s][++R[s][0]]=i;  //adaug muchia la subgraf
        }
    }

    flux=DFS(1,last);  //bag flux in retea

    last-=flux;
    return flux;
}
int main()  //algoritmul lui DINIC
{
    freopen ("maxflow.in","r",stdin);
    freopen ("maxflow.out","w",stdout);
    citire();
    do
    {
        now=dinic();
        flux+=now;
    }while (now>0); //cat timp mai putem baga flux
    printf("%i",flux);
    fclose(stdin);
    fclose(stdout);
    return 0;
}