#include<iostream>
#include<fstream>
#include<vector>
#include<algorithm>

using namespace std;

ofstream g("maxflow.out");

int flux[1002][1002],cap[1002][1002],sw[1002],C[1000000],t[1002],n,mc[1002][1002];

vector<int> v[1005],sol;

int solve(int x, int y)
{
	vector<int> :: iterator it;
	int gasit=0;
	int p,u,i;
	C[1]=1;
	p=u=1;
	memset(sw,0,sizeof(sw));
	sw[1]=1;
	
	while(p<=u)
	{
		for (it=v[C[p]].begin();it<v[C[p]].end();++it)
			if (sw[*it]==0 && cap[C[p]][*it]>flux[C[p]][*it])
			{
				sw[*it]=1;
				C[++u]=*it;
			}
		++p;
	}
	gasit+=sw[x];
	
	memset(sw,0,sizeof(sw));
	p=u=1;
	C[p]=n;
	
	while(p<=u)
	{
		for (it=v[C[p]].begin();it<v[C[p]].end();++it)
			if (sw[*it]==0 && cap[C[p]][*it]>flux[C[p]][*it])
			{
				sw[*it]=1;
				C[++u]=*it;
			}
		p++;
	}
	
	gasit +=sw[y];
	return (gasit==2);
}

void critice()
{
	int i,j,gasit;
	for (i=1;i<=n;i++)
		for (j=i+1;j<=n;j++)
		{
			if (cap[i][j]==flux[i][j] && mc[i][j]>0)
			{
				gasit=solve(i,j);
				if (gasit)
				{
					cout<<i<<' '<<j<<endl;
					sol.push_back(mc[i][j]);
			}}
			else
				if (cap[j][i]==flux[j][i])
				{
					gasit=solve(j,i);
					if (gasit)
				{ cout<<j<<' '<<i<<endl;		sol.push_back(mc[j][i]);
				}}
		}
}

int Flux ()
{
	vector<int> :: iterator it;
	int k,i,p,u,gasit,fmax;
	C[1]=1;
	memset(sw,0,sizeof(sw));
	sw[1]=1;
	p=u=1;
	while(p<=u)
	{
		for (it=v[C[p]].begin();it<v[C[p]].end();++it)
			if ((sw[*it]==0) && (cap[C[p]][*it]>flux[C[p]][*it]) && (*it!=n))
			{
				if (sw[*it]==0)
				{
					C[++u]=*it;
					sw[*it]=1;
				}
				t[*it]=C[p];
			}
		p++;
	}

	gasit=0;
	for (i=1;i<=n;i++)
		if (cap[i][n]>0 && sw[i]==1 && cap[i][n]>flux[i][n])
		{
			fmax=cap[i][n]-flux[i][n];
			k=i;
			while (k>1)
			{
				fmax=min(fmax, cap[t[k]][k]-flux[t[k]][k]);
				k=t[k];
			}
			
			gasit+=fmax;
			
			k=i;
			flux[i][n]+=fmax;
			flux[n][i]-=fmax;
			
			while (k>1)
			{
				flux[t[k]][k]+=fmax;
				flux[k][t[k]]-=fmax;
				k=t[k];
			}
		}
	return gasit;
}		

void fluxmaxim()
{
	int i,s=0;
	i=1;
	while (i!=s)
	{
		i=s;
		s+=Flux();
	}
	g<<s;
	g.close();
}

void afisare()
{
	vector<int> ::iterator it;
	
	
	g<<sol.size()<<'\n';
	sort(sol.begin(),sol.end());
	
	for (it=sol.begin();it<=sol.end()-1;it++)
		g<<*it<<'\n';
	
	g.close();
}


void citire()
{
	int i,x,y,m,c;
	ifstream f("maxflow.in");
	f>>n>>m;
	
	for (i=1;i<=m;i++)
	{
		f>>x>>y>>c;
		mc[x][y]=mc[y][x]=i;
		cap[x][y]=c;
		v[x].push_back(y);
	}
	f.close();
}

int main()
{
	citire();
	fluxmaxim();
	//critice();
	
	return 0;
}