//apm cu algoriitmul lui prim
#include<fstream>
#include<vector>
#define infin 250000003

using namespace std;
ifstream fin("apm.in");
ofstream fout("apm.out");

int v[200002], s[200002], pret[200002], arb[525000], n, mm, sol;
 
struct muchie
{
    int inf;
    int cost;
};
      
vector <muchie> lv[200002];
  
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;
}