#include <stdio.h>
#include <vector>
#include<string.h>
#include<algorithm>
#define pb push_back
using namespace std;
vector < long > G[1001];
long n,m,i,j,x,y,z,C[1001][1001],F[1001][1001],VIZ[1001],PCT[1001];
long Q[10001],dim,k,V,U,sz,TT[1001],sol,X,MIN,numar;
int BFS()
{
    dim=1;
    Q[1]=1;
    memset(TT,0,sizeof TT);
    memset(VIZ,0,sizeof VIZ);
    VIZ[1]=1;
    sol=0;
    for (k=1;k<=dim;k++)
    {
        U=Q[k];
        sz=G[U].size();
        for (i=0;i<sz;i++)
        {
           V=G[U][i];
           if (V==n) {sol=1;continue;}
           if (C[U][V]>0&&!VIZ[V])
           {
                TT[V]=U;
                VIZ[V]=1;
                Q[++dim]=V;
           }
        }
    }
    return sol;
}
long has_sol;
void DFS(long U)
{
    int i,V,sz;
    sz=G[U].size();
    for (i=0;i<sz;i++)
    {
        V=G[U][i];
        if (V==n)
            if (has_sol==1)
            {
                if (PCT[sol]==0)
                {
                    PCT[sol]=1;
                    numar++;
                }
            }
        if (VIZ[V]==1)
            continue;
        if (C[V][U]==0)
        {
            if (has_sol==0)
            {
                has_sol=1;
                sol=V;
                VIZ[V]=1;
                if (PCT[sol]==0)
                    DFS(V);
                VIZ[V]=0;
                has_sol=sol=0;
            }
        }
        else
        {
            VIZ[V]=1;
            if (PCT[sol]==0)
                DFS(V);
            VIZ[V]=0;
        }
    }
}
int main()
{
    freopen ("critice.in","r",stdin);
    freopen ("critice.out","w",stdout);
    scanf ("%ld%ld",&n,&m);
    for (i=1;i<=m;i++)
    {
        scanf ("%ld%ld%ld",&x,&y,&z);
        G[x].pb(y);
        G[y].pb(x);
        C[x][y]=C[y][x]=z;
        F[x][y]=F[y][x]=z;
    }
    while (BFS())
    {
        U=n;
        sz=G[U].size();
        for (i=0;i<sz;i++)
        {
            V=G[U][i];
            TT[U]=V;
            if (!TT[V])
                continue;
            X=n;
            MIN=999999999;
            while (TT[X])
            {
                MIN=min(MIN,C[X][TT[X]]);
                X=TT[X];
            }
            X=n;
            while (TT[X])
            {
                C[X][TT[X]]-=MIN;
                C[TT[X]][X]-=MIN;
                X=TT[X];
            }
        }
    }
    memset(VIZ,0,sizeof VIZ);
    VIZ[1]=1;
    numar=0;
    has_sol=0;
    sol=0;
    DFS(1);
    printf ("%ld",numar);
    return 0;
}