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

using namespace std;

#define Nmax 200010

struct muchie {int e1,e2,cost;} g[2*Nmax];
int n,m; 
char v[2*Nmax];
int costapm;
int t[Nmax],t1,t2,nr,i;

int cmp(muchie a, muchie b)
{   
  return a.cost<b.cost;   
}   

int tata(int x)
{
	while(t[x]>0)
		  x=t[x];
	return x;
}

int main()
{
	freopen("apm.in","r",stdin);
	scanf("%d %d", &n,&m);
	for (i=1;i<=m;++i)
		scanf("%d %d %d", &g[i].e1, &g[i].e2, &g[i].cost);
	fclose(stdin);
	
	sort(g+1,g+1+m,cmp);
		for (i=1;i<=n;++i)
		 t[i]=-1;
	
	for(i=1;i<=m && nr!=n-1;++i)
	{   
     t1=tata(g[i].e1);   
     t2=tata(g[i].e2);   
      
     if (t1!=t2)
	 {   
       costapm+=g[i].cost;   
	   t[t1]=t2;
       v[i]=1;   
       nr++;   
     }   
    }
	
	freopen("apm.out","w",stdout);
	printf("%d\n", costapm);
	printf("%d\n", n-1);
	for (i=1;i<=m;++i)
		if (v[i])
		 printf("%d %d\n", g[i].e2,g[i].e1);
	
	fclose(stdout);
	
	return 0;
}