//cu algoritmul lui prim
#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], arb[132000], 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;
}