#include <stdio.h>
#include <string.h>

int c[1005][1005];

int nr[1005][1005];
int lm[1005][1005];
int nrm[1005];

int posibil1[1005],posibil2[1005];
int care[10005];

int main()
{
    freopen("critice.in","r",stdin);
    freopen("critice.out","w",stdout);

    int n,m;
    scanf("%d %d",&n,&m);

    for (int i=1; i<=m; ++i)
    {
        int x,y,z;
        scanf("%d %d %d",&x,&y,&z);

        c[x][y]=z;
        c[y][x]=z;
        nr[x][y]=i;
        nr[y][x]=i;

        ++nrm[x];
        lm[x][nrm[x]]=y;

        ++nrm[y];
        lm[y][nrm[y]]=x;
    }

    int marit=1;
        int parcurs[1005],l;
        int trecut[1005];
        int candidat[1005],nr_c;
        int prec[1005];


    while (marit > 0)
    {
        marit=0;

        memset(trecut,0,1005*sizeof(int));
        nr_c=0;

        l=1;
        parcurs[l]=1;
        trecut[1]=1;

        int i=1;
        while (i <= l)
        {
            int nod=parcurs[i];
            for (int j=1; j<=nrm[nod]; ++j)
            {
                if (trecut[lm[nod][j]]==0 && c[nod][lm[nod][j]]>0)
                {
                    ++l;
                    parcurs[l]=lm[nod][j];
                    trecut[lm[nod][j]]=1;
                    prec[lm[nod][j]]=nod;
                }
            }

            if (c[nod][n]>0)
            {
                ++nr_c;
                candidat[nr_c]=nod;
            }

            ++i;
        }

        for (int i=1; i<=nr_c; ++i)
        {
            int minim=c[candidat[i]][n];

            int nod=candidat[i];
            while (nod != 1)
            {
                if (c[prec[nod]][nod]<minim)
                {
                    minim=c[prec[nod]][nod];
                }
                nod=prec[nod];
            }

            nod = candidat[i];
            c[nod][n]-=minim;
            c[n][nod]+=minim;
            while (nod != 1)
            {
                c[prec[nod]][nod]-=minim;
                c[nod][prec[nod]]+=minim;
                nod=prec[nod];
            }

            marit+=minim;
        }
    }

  /*  memset(trecut,0,1005*sizeof(int));
    trecut[1]=1;
    parcurs[1]=1;
    l=1;
    int i=1;
    posibil1[1]=1;
    while (i<=l)
    {
        int nod=parcurs[i];
        for (int j=1; j<=n; ++j)
        {
            if (trecut[j]==0 && c[nod][j]>0)
            {
                ++l;
                parcurs[l]=j;
                trecut[j]=1;
                posibil1[j]=1;
            }
        }
        ++i;
    }

    memset(trecut,0,1005*sizeof(int));
    trecut[n]=1;
    parcurs[1]=n;
    l=1;
    i=1;
    posibil2[n]=1;
    while (i<=l)
    {
        int nod=parcurs[i];
        for (int j=1; j<=n; ++j)
        {
            if (trecut[j]==0 && c[j][nod]>0)
            {
                ++l;
                parcurs[l]=j;
                trecut[j]=1;
                posibil2[j]=1;
            }
        }
        ++i;
    }

    memset(care,0,10005*sizeof(int));
    l=0;
    for (int i=1; i<=n; ++i)
    {
        for (int j=1; j<=n; ++j)
        {
            if (c[i][j]==0 && posibil1[i]==1 && posibil2[j]==1 && care[nr[i][j]]==0 && nr[i][j]>0)
            {
                care[nr[i][j]]=1;
                ++l;
            }
        }
    }

    printf("%d\n",l);
    for (int i=1; i<10005; ++i)
    {
        if (care[i]==1)
        {
            printf("%d\n",i);
        }
    }*/

    fclose(stdin);
    fclose(stdout);

    return 0;
}