#include<fstream>
#include<vector>
#define infin 250000003
using namespace std;
 
 
 
ifstream fin("apm.in");
ofstream fout("apm.out");
int v[50002],s[50002];

struct muchie
{
    int inf;
    int cost;
};
     
vector <muchie> lv[50002];
int pret[50002];
int arb[132000];
int n,mm,sol;
 
 
void actualizare(int nod,int st,int dr,int x,int cost)
{if(st==dr)arb[nod]=cost;
   else
   {
    int m;
    m=(st+dr)/2;
    if(x<=m)actualizare(2*nod,st,m,x,cost);
       else actualizare(2*nod+1,m+1,dr,x,cost);
     if(arb[2*nod]<arb[2*nod+1])arb[nod]=arb[2*nod];
        else arb[nod]=arb[2*nod+1];
   }
}
     
void construire(int nod,int st, int dr)
{if(st==dr){if(st==1)arb[nod]=0;
               else arb[nod]=infin;
            if(st!=1)
			pret[st]=infin;
			   else pret[st]=0;
            }
    else{
        int m;
        m=(st+dr)/2;
        construire(nod*2,st,m);
        construire(nod*2+1,m+1,dr);
        if(arb[2*nod]<arb[2*nod+1])arb[nod]=arb[2*nod];
         else arb[nod]=arb[2*nod+1];
         
        }
}
         
int minim(int nod, int st,int dr)
{if(st==dr)return st;
  else
  {
      int m;
      m=(st+dr)/2;
      if(arb[2*nod]<arb[2*nod+1])return minim(2*nod,st,m);
         else return minim(2*nod+1,m+1,dr);
  }
}
 
int main()
{
    int i;
     
    fin>>n;
    fin>>mm;
    for(i=1;i<=mm;i++)
    {  
        int x;
        muchie y;
        fin>>x>>y.inf>>y.cost;
        lv[x].push_back(y);
		int aux;
		aux=x;
		x=y.inf;
		y.inf=aux;
		lv[x].push_back(y);
         
    }
     
    int j;
    
    construire(1,1,n);
    while(arb[1]!=infin)
    {
         int cine,cat;
         cine=minim(1,1,n);
         pret[cine]=arb[1];
		 sol+=pret[cine];
         v[cine]=1;
         cat=lv[cine].size();
         for(i=0;i<cat;i++)
         {
          
             if(!v[lv[cine][i].inf] && lv[cine][i].cost < pret[lv[cine][i].inf])
             {
                 pret[lv[cine][i].inf]=lv[cine][i].cost;
				 s[lv[cine][i].inf]=cine;
                 actualizare(1,1,n,lv[cine][i].inf,pret[lv[cine][i].inf]);
             }
         }
         actualizare(1,1,n,cine,infin);
     }
      
    fout<<sol<<"\n";
	fout<<n-1<<"\n";
     for(i=2;i<=n;i++)
        fout<<i<<" "<<s[i]<<"\n";         
          
     
    return 0;
}