#include <cstdio>
#include <algorithm>

using namespace std;

#define file_in "apm.in"
#define file_out "apm.out"

#define Nmax 200010
#define ii inline

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

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

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

void citire()
{
	int i;
	
	freopen(file_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);
}

void solve()
{
	int i,nr;
	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;   
       if (t[t1]<t[t2])
	   {   
         t[t2]+=t[t1];   
         t[t1]=t2;   
       }   
       else
	   {   
         t[t1]+=t[t2];   
         t[t2]=t1;   
       }   
       v[i]=1;   
       nr++;   
     }   
    }
	
}

void afisare()
{
	int i;
	freopen(file_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);
}

int main()
{
	
	citire();
    solve();
    afisare();

	fclose(stdin);
	fclose(stdout);
	
	return 0;
}