#include <stdio.h>

//asta cica e infinit... imi place cum arata
#define oo 1000000000

#define N 1000
#define M 10000

inline void swap(int& x, int& y)
{
	int aux = x;
	x = y;
	y = aux;
}

inline int abs(int x)
{
	if(x>=0) return x;
	return -x;
}

inline int min(int x, int y)
{
	if(x>y) return y;
	return x;
}

struct muchie { int x, y; };
FILE *fo = fopen("critice.out","w");
int a[N+1][N+1]; //liste de adiacenta
int c[N+1][N+1]; //capacitati
int f[N+1][N+1]; //flux
int n,m;
int fluxMax;
muchie vm[M+1];

int viz[N+1], pred[N+1], critice[M+1], d1[N+1], d2[N+1];

//coditza pentru breadth first
int queue[N+2], head, tail;
void enqueue(int x, int *vector_viz)
{
	queue[tail]=x;
	++tail;
	vector_viz[x]=1;
}

int dequeue()
{
	int e = queue[head];
	++head;
	return e;	
}
//end of coditza

int breadth_first_1()
{
	//start : 1, end : n
	int i,e,v;
	for(i=1;i<=n;++i) viz[i]=0;
	head = tail = 0;
	enqueue(1,viz);
	pred[1] = 0;
	while(head != tail)
	{
		e = dequeue();
		for(i=1;i<=a[e][0];++i)
		{
			v = a[e][i];
			if( ( ! viz [ v ] ) && c[e][v] - f[e][v] > 0  )
			{
				enqueue(v,viz);
				pred[v] = e;
				if(v==n) break;
			}
		}
	}
	return viz[n];
}

void breadth_first_2(int sursa, int *vector_viz)
{
	int i,e,v;
	for(i=1;i<=n;++i) vector_viz[i]=0;
	head = tail = 0;
	enqueue(sursa, vector_viz);
	while(head != tail)
	{
		e = dequeue();
		for(i=1;i<=a[e][0];++i)
		{
			v = a[e][i];
			if( ( ! vector_viz [ v ] ) && c[e][v] - abs(f[e][v]) > 0 ) enqueue(v, vector_viz);
		}
	}
}

int ford_fulkerson()
{
	int i,j,inc;
	int u;
	int max_flow = 0;
	for(i=1;i<=n;++i) for(j=1;j<=n;++j) f[i][j] = 0;
	while(breadth_first_1())
	{
		inc = oo;
		for(u=n; pred[u]>0; u=pred[u]) inc = min(inc, c[pred[u]][u] - f[pred[u]][u]);
		for(u=n; pred[u]>0; u=pred[u])
		{
			f[pred[u]][u] += inc;
			f[u][pred[u]] -= inc;
		}		
		max_flow += inc;
	
	}
	fluxMax = max_flow;
}

inline void citeste()
{
	FILE *fi = fopen("critice.in","r");
	fscanf(fi, "%d%d", &n, &m);
	int x,y,capacitate;
	for(int i=1;i<=m;++i)
	{
		fscanf(fi, "%d%d%d", &x, &y, &capacitate);
		
		vm[i].x=x;
		vm[i].y=y;
		
		c[x][y] = c[y][x] = capacitate;
		
		a[x][++a[x][0]]=y;
		a[y][++a[y][0]]=x;
	}
	fclose(fi);
}

void rezolva()
{
	int x, y;
	int i;
	ford_fulkerson();
	breadth_first_2(1, d1);
	breadth_first_2(n, d2);
	for(i=1;i<=m;++i)
	{
		x = vm[i].x;
		y = vm[i].y;
		if((d1[x] && d2[y]) || (d2[x] && d1[y])) critice[++critice[0]] = i;
	}
}

void scrie()
{
	FILE *fo = fopen("critice.out","w");
	/*
	fprintf(fo, "%d\n", critice[0]);
	for(int i=1;i<=critice[0];++i) fprintf(fo, "%d\n", critice[i]);
	*/
	fprintf(fo, "%d\n",fluxMax);	
	fclose(fo);
}
int main()
{
	citeste();
	rezolva();
	scrie();
	
	
	return 0;
}