#include <fstream>

using namespace std;

ifstream cin("apm.in");
ofstream cout("apm.out");

int N,M,C,X,Y;
int tata[100005];
bool ok[100005];
struct costuri
{
 int nod1,nod2;
 costuri* next;
}*L[2005];
struct muchie
{
 int nod1,nod2,cost;
}linie[100004];
int multime(int x)
{
 int copiex=x;
 while(tata[x]>0)
 {
  x=tata[x];
 }
 while(tata[copiex]!=x && tata[copiex]>0)
 {
  int aux=tata[copiex];
  tata[copiex]=x;
  copiex=aux;
 }
 return x;
}
void unire(int x,int y)
{
 int tatasupremx=multime(x);
 int tatasupremy=multime(y);
 if(tata[tatasupremx]>tata[tatasupremy])
 {
  tata[tatasupremy]+=tata[tatasupremx];
  tata[tatasupremx]=tatasupremy;
 }
 else
 {
 tata[tatasupremx]+=tata[tatasupremy];
  tata[tatasupremy]=tatasupremx;
 }
}
bool linieebuna(int x,int y)
{
 if(multime(x)==multime(y))
 return false;
 else
 return true;
}
int main()
{
    cin>>N>>M;
    for (int i = 1; i <= N; ++i)
			tata[i] = -1;
    for(int i=1;i<=M;++i)
    {
     cin>>X>>Y>>C;
     costuri* alocare=new costuri;
     alocare->nod1=X;
     alocare->nod2=Y;
     alocare->next=L[C+1000];
     L[C+1000]=alocare;
    }
    int k=0;
    for(int i=0;i<=2000;++i)
    {
     for(costuri* a=L[i];a!=NULL;a=a->next)
			 {
				++k;
			  linie[k].nod1=a->nod1;
			  linie[k].nod2=a->nod2;
			  linie[k].cost=i;
			  }
    }
    int costtotal=0;
    int muchiitotale=0;
    for(int i=1;i<=k;++i)
    {
     if(linieebuna(linie[i].nod1,linie[i].nod2)==true)
     {
      costtotal+=linie[i].cost;
      costtotal-=1000;
      muchiitotale+=1;
      unire(linie[i].nod1,linie[i].nod2);
			ok[i]=true;
     }
    }
    cout<<costtotal<<'\n';
    cout<<muchiitotale<<'\n';
    for(int i=1;i<=M;++i)
    {
     if(ok[i]==true)
      cout<<linie[i].nod1<<' '<<linie[i].nod2<<'\n';
    }
    return 0;
}