#include<fstream>
#define MAXN 400005
#define LL long long
using namespace std;
#define LL long long
 ifstream cin("apm.in");
 ofstream cout("apm.out");
LL M,N,X[MAXN],Y[MAXN],C[MAXN],k;
LL ARBX[MAXN],ARBY[MAXN]; 
  void poz(LL li,LL ls,LL &k)
  {
   	   int i=li,j=ls,aux,i1=0,j1=-1;
   	   while(i<j)
   	   {    if(C[i]>C[j])
   	        {
			 //cost schimbare			 
			 aux=C[j];
			 C[j]=C[i];
			 C[i]=aux;
			 //schimbare X[i]
		     aux=X[j];
			 X[j]=X[i];
			 X[i]=aux;
			 //schimbare Y[i]
			 aux=Y[j];
			 Y[j]=Y[i];
			 Y[i]=aux;
			 aux=i1;
			 i1=-j1;
			 j1=-aux;
			 }
			 i=i+i1;
			 j=j+j1;
			 }//end while
		 k=i;		 
	 }//end poz
	 void quick(LL li,LL ls)
	 { if(li<ls)
	 { poz(li,ls,k);
	  quick(li,k-1);
	  quick(k+1,ls);
	  }
     } 
//find  
LL TT[MAXN],RG[MAXN];
int Find(int x)
{
    int R, y;
    for (R = x; TT[R] != R; R = TT[R]);
     for (; TT[x] != x;)
    {
        y = TT[x];
        TT[x] = R;
        x = y;
    }
    return R;
}
//unite
void Union(int x, int y)
{
    if (RG[x] > RG[y])
        TT[y] = x;
            else TT[x] = y;
    if (RG[x] == RG[y]) RG[y]++;
}   
  int main() {
  	  LL i,j;
  	  LL S=0,it=0;
  	 cin>>N>>M;
	 for(i=1;i<=M;i++)
	  cin>>X[i]>>Y[i]>>C[i];
	 quick(1,M);
	  for (i = 1; i <= N; i++)
    {
        TT[i] = i;
        RG[i] = 1;
    }
     for(i=1;i<=M;i++)
            if(Find(X[i])!=Find(Y[i]))  {
					++it;			 
                  ARBX[it]=X[i];
                  ARBY[it]=Y[i];
                  Union(Find(X[i]),Find(Y[i]));
                  S+=C[i];
				  }
	cout<<S<<"\n";
	cout<<it<<"\n";
	for(i=1;i<=it;i++)
	   cout<<ARBX[i]<<" "<<ARBY[i]<<"\n";			  			     
	   return 0;
	   }