#include<fstream>
#include<vector>
#include<iterator>
#include<math.h>
using namespace std;

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

# define nmax 1002
# define INF 10002
# define Min(a,b) ((a)<(b)? (a):(b))

vector <int> v[nmax];
vector <int>::const_iterator it;
int N,M,C[nmax][nmax],F[nmax][nmax],t[nmax],Q[nmax],K;
bool viz[nmax];

void citire()
{
	f>>N>>M;
	int i,j,c;
	for(;M;--M)
	{
		f>>i>>j>>c;
		v[i].push_back(j);
		v[j].push_back(i);
		C[i][j]=C[j][i]=c;
	}
}
int BF(int S,int D)
{
	memset(viz,0,sizeof(viz));
	memset(t,0,sizeof(t));
	int st=0,dr=0,nod;
	Q[0]=S;
	while(st<=dr)
	{
		nod=Q[st++];
		for(it=v[nod].begin();it<v[nod].end();++it)
			if(!viz[*it]&&C[nod][*it]>F[nod][*it])
			{
				viz[*it]=1;
				Q[++dr]=*it;
				t[*it]=nod;
				if(*it==D) return 1;
			}
	}
	return 0;
}
void edmond_karp(int S,int D)
{
	int i,m,flux=0;
	while(BF(S,D))
	{
		m=INF;
		for(i=D;i!=S;i=t[i])
			m=Min(m,C[t[i]][i]-F[t[i]][i]);
		for(i=D;i!=S;i=t[i])
			F[t[i]][i]+=m,
			F[i][t[i]]-=m;
		flux+=m;
	}
}
void bf(int S,int D)
{
	memset(t,0,sizeof(t));
	t[S]=S, t[D]=D;
	Q[0]=S;
	int st=0,dr=0,nod;
	while(st<=dr)
	{
		nod=Q[st++];
		for(it=v[nod].begin();it<v[nod].end();++it)
			if(!t[*it] && C[nod][*it]>F[nod][*it])
			{
				Q[++dr]=*it;
				t[*it]=t[nod];
			}
	}
	Q[0]=D;
	st=dr=0;
	while(st<=dr)
	{
		nod=Q[st++];
		for(it=v[nod].begin();it<v[nod].end();++it)
			if(!t[*it] && C[nod][*it]>F[nod][*it])
			{
				Q[++dr]=*it;
				t[*it]=t[nod];
			}
			else if(C[nod][*it]==abs(F[nod][*it]) && t[nod]==D && t[*it]==S) ++K;
	}
}
int main()
{
	citire();
	edmond_karp(1,N);
	bf(1,N);
	
	g<<K<<'\n';
	f.close();
	ifstream ff("critice.in");
	ff>>N>>M;
	int i,j,c,m;
	for(m=1;m<=M;++m)
	{
		ff>>i>>j>>c;
		if((F[i][j]==C[i][j]||F[j][i]==C[j][i])&& ((t[i]==1&&t[j]==N)||(t[i]==N&&t[j]==1)))
			g<<m<<'\n';
	}
}