#include<fstream>
#include<algorithm>
#define MAXN 400005
#define LL long long
using namespace std;
#define LL long long
 ifstream cin("apm.in");
 ofstream cout("apm.out");
LL N,M,NLL,TT[MAXN],RG[MAXN]; 
struct muchie {
	   int X,Y,C;
} G[MAXN],A[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 cmp(muchie a,muchie b){ return (a.C<b.C);}  
  int main() {
  	  LL i,S=0,it=0;
  	 cin>>N>>M;
	 for(i=1;i<=M;i++)
	  cin>>G[i].X>>G[i].Y>>G[i].C;
	  sort(G+1,G+M+1,cmp);
	// for(i=1;i<=M;i++)
	 // cout<<G[i].X<<" "<<G[i].Y<<" "<<G[i].C<<"\n"; 
	  for (i = 1; i <= N; i++)
    {
        TT[i] = i;
        RG[i] = 1;
    }
     for(i=1;i<=M;i++)
            if(Find(G[i].X)!=Find(G[i].Y))  {
					++it;			 
                  A[it].X=G[i].X;
                  A[it].Y=G[i].Y;
                  Union(Find(G[i].X),Find(G[i].Y));
                  S+=G[i].C;
				  }
	cout<<S<<"\n";
	cout<<it<<"\n";
	for(i=1;i<=it;i++)
	   cout<<A[i].X<<" "<<A[i].Y<<"\n";			  			     
	   return 0;
	   }