#include<stdio.h>
#include<math.h>
#include<iomanip.h>
#define max 51
typedef struct nod{
int info;
nod*urm;
}*PNOD,NOD;
PNOD l[max];
int c[max][max],f[max][max],cr[max],s[max],t[max];
int q[max],o[max][max];
int s0[max],s1[max];
int n,m;
int flux1=0;
void citire();
void edmondskarp();
int flux();
int min(int ,int );
void afisare();
void dfstanga(int nod);
void dfdreapta(int nod);
void add(int ,int );
void drum();
int main()
{
freopen("critice.in","r",stdin);
freopen("critice.out","w",stdout);
citire();
edmondskarp();
afisare();
return 0;
}
void citire()
{
int i,x,y,cost;
scanf("%d %d",&n,&m);
for(i=1;i<=m;i++)
{
scanf("%d %d %d",&x,&y,&cost);
c[x][y]=cost;
}
/*
for(i=1;i<=m;i++)
{
for(int j=1;j<=m;j++)
printf("%d ",c[i][j]);
printf("\n");
}
*/
}
int min(int a,int b)
{
if(a<=b) return a;
else
return b;
}
int flux()
{
memset(s,0,sizeof(s));
memset(cr,0,sizeof(cr));
memset(t,0,sizeof(t));
memset(q,0,sizeof(q));
int p,u,i,j;
p=u=0;
s[1]=1;
t[1]=0;
q[p]=1;
cr[1]=32000;
while(p<=u)
{
i=q[p];
for(j=1;j<=n;j++)
if(!s[j])
{
if(c[i][j]>f[i][j])
{
cr[j]=min(c[i][j]-f[i][j],cr[i]);
q[++u]=j;
s[j]=1;
t[j]=i;
if(j==n) return 1;
}
if(f[j][i])
{
cr[j]=min(f[j][i],cr[i]);
q[++u]=j;
s[j]=1;
t[j]=-i;
if(j==n) return 1;
}
}
p++;
}
return 0;
}
void edmondskarp()
{
while(flux())
drum();
}
void drum()
{
int i,j;
i=n;
while(i)
{
j=abs(t[i]);
if(t[i]>0) f[j][i]+=cr[n];
else
f[i][j]-=cr[n];
i=j;
}
flux1+=cr[n];
}
void afisare()
{
int i,j,nrsol=0;
//printf("%d\n",flux1);
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
if(c[i][j]!=0 && c[i][j]==f[i][j])
{
nrsol++;
dfstanga(i);
dfdreapta(j);
printf("%d %d",i,j);
printf("\n");
//add(i,j);
//add(j,i);
}
}
printf("%d\n",nrsol);
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
if(c[i][j]!=0 && c[i][j]!=f[i][j])
{
add(i,j);
add(j,i);
}
}
//for(PNOD p=l[5];p;p=p->urm)
//printf("%d ",p->info);
}
void add(int i,int j)
{
PNOD p=new NOD;
p->info=j;
p->urm=l[i];
l[i]=p;
}
void dfstanga(int nod)
{
s0[nod]=1;
for(int i=1;i<=n;i++)
if(!s0[i]&& c[nod][i])
dfstanga(i);
}
void dfdreapta(int nod)
{
s1[nod]=1;
for(int i=1;i<=n;i++)
if(!s1[i] && c[nod][i])
dfdreapta(i);
}