#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);
}