#include<stdio.h>  
  #include<algorithm>  
   #include<vector>  
   #define pb push_back  
     
   using namespace std;  
     
    const int maxn = 400100;  
      
   int GR[maxn],X[maxn],Y[maxn],C[maxn];  
   int N,M,ANS,IND[maxn];  
   vector<int> VANS;  
     
   int grupa(int i)  
   {  
       if (GR[i] == i) return i;  
       GR[i] = grupa(GR[i]);  
       return GR[i];  
   }  
     
   void reuniune(int i,int j)  
   {  
       GR[grupa(i)] = grupa(j);   
   }  
     
   bool cmpf(int i,int j)  
   {  
       return(C[i] < C[j]);   
   }  
     
   int main()  
   {  
       freopen("apm.in","r",stdin);  
       freopen("apm.out","w",stdout);  
       scanf("%d %d\n",&N,&M);  
       for(int i = 1;i <= M;++i)  
       {  
           scanf("%d %d %d\n",&X[i],&Y[i],&C[i]);  
           IND[i] = i;  
       }  
     
       for(int i = 1;i <= N; ++i) GR[i] = i;  
       for(int i = 1;i <= N; ++i) GR[i] = i;  
       sort(IND + 1,IND + M + 1,cmpf);  
       for(int i = 1;i <= M; ++i)  
       {  
           if (grupa(X[IND[i]]) != grupa(Y[IND[i]])){  
               ANS += C[IND[i]];reuniune(X[IND[i]],Y[IND[i]]);  
               VANS.pb(IND[i]);  
           }  
       }  
       printf("%d\n",ANS);  
       printf("%d\n",N - 1);  
       for(int i = 0;i < N - 1; ++i)  
           printf("%d %d\n",X[VANS[i]],Y[VANS[i]]);  
       return 0;  
   }