#include<stdio.h>
#include<vector>
#include<algorithm>

using namespace std;
const int maxn=400001;
int x[maxn],y[maxn],cost[maxn],indice[maxn],gr[maxn],n,m,rez;
vector<int>Apm;
int padure(int i)
{
if (gr[i]==i)  return i;
gr[i]=padure(gr[i]);
return gr[i];    
}

void reun(int i, int j)
{
gr[padure(i)]=padure(j);    
}

inline bool cmp(int i, int j)
{
return cost[i]<cost[j];       
}


int main()
{
    int i;
freopen("apm.in","r",stdin);
freopen("apm.out","w",stdout);
 scanf("%d %d\n",&n,&m);
 
 for(i=1;i<=m;i++)
 {
   scanf("%d %d %d\n",&x[i],&y[i],&cost[i]);
   indice[i]=i;                 
 }
 
 for(i=1;i<=n;i++)
 gr[i]=i;
 sort(indice+1, indice+1+m,cmp);
 for(i=1;i<=m;i++)
   if(padure(x[indice[i]])!=padure(y[indice[i]]))
   {
     rez+=cost[indice[i]];
     reun(x[indice[i]],y[indice[i]]);
     Apm.push_back(indice[i]);                                               
   }
   
   printf("%d\n%d\n",rez, n-1);
   
   for(i=0;i<n-1;i++)
   printf("%d %d\n",x[Apm[i]],y[Apm[i]]);
   
   
 
 return 0;   
}