# include <fstream>
# include <algorithm>
# include <vector>
# include <queue>
# include <cstring>
# define NR 1005
# define inf 999999999
using namespace std;
ifstream f("maxflow.in");
ofstream g("maxflow.out");
vector <int> v[NR];
queue <int> q;
int i,j,n,m,flux,S,D,x,y,minn,VV;
int T[NR], c[NR][NR], F[NR][NR], sol[11*NR], ap[NR][NR], cpy[100];
bool bfs ()
{
    int i,j,k,urm,ok=0;
    memset (T, 0, sizeof(T));

    T[S]=-1; q.push(S);
    while (! q.empty())
    {
        k=q.front(); q.pop();
        for (i=0; i<v[k].size(); ++i)
        {
            urm=v[k][i];
            if (T[urm]==0 && c[k][urm]>F[k][urm])
            {
                if (urm==D) ok=1;
                else {
                         T[urm]=k;
                         q.push(urm);
                     }
            }
        }
    }
    return ok;
}
int dinic ()
{
   int i, flux=0;
   while(bfs())
   {
       for (i=0; i<v[D].size(); ++i)
       {
           int ant=v[D][i];
           if (T[ant]!=0 && c[ant][D]>F[ant][D])
           {
               T[D]=ant; minn=inf;
               for (int nod=D; nod!=S; nod=T[nod])
                   minn=min (minn, c[T[nod]][nod] - F[T[nod]][nod]);

               if (minn<=0) continue;

               flux+=minn;

               for (int nod=D; nod!=S; nod=T[nod])
               {
                   F[T[nod]][nod]+=minn;
                   F[nod][T[nod]]-=minn;
               }
           }
       }
   }
   return flux;
}
void curata ()
{
    for (int i=1; i<=n; ++i)
        for (int j=0; j<v[i].size(); ++j)
        {
            int x=i, y=v[i][j];
            F[x][y]=F[y][x]=0;
        }
}
int main ()
{
    f>>n>>m;
    for (i=1; i<=m; ++i)
    {
        f>>x>>y; f>>c[x][y];

        ap[x][y]=ap[y][x]=i;

        v[x].push_back(y);
        v[y].push_back(x);
    }

    S=1; D=n;

    g<<dinic();
    /*for (i=1; i<=n; ++i)
        cpy[i]=F[S][i];

    for (i=0; i<v[S].size(); ++i)
    {
        int urm=v[S][i];
        if (cpy[urm]==c[S][urm]) //daca aici e flux maxim
        {
            curata ();
            int x=S, y=urm;
            ++c[x][y]; ++c[y][x];

            int flux=dinic ();
            if (flux>FLUX) sol[++VV]=ap[x][y];

            --c[x][y]; --c[y][x];
        }
    }

    //g<<flux<<"\n";

    sort (sol+1, sol+VV+1);
    g<<VV<<"\n";
    for (i=1; i<=VV; ++i)
        g<<sol[i]<<"\n";*/


    return 0;
}