#include <cstdio>
#include <vector>
#include <algorithm>

using namespace std;

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

#define Nmax 400010

int n,m;
int cost;
int sol[Nmax];
int x[Nmax];
int y[Nmax];
int c[Nmax];
int ind[Nmax];
int tata[Nmax],nr;

int find(int x)
{
	if (tata[x]!=x)	
		tata[x]=find(tata[x]);
	return tata[x];
}

void unite(int i , int j)
{
	tata[i]=j;
}
	
int cmp(int a, int b)
{
	return c[a]<c[b];
}

int main()
{
	int i,t1,t2;
	freopen(file_in,"r",stdin);
	freopen(file_out,"w",stdout);
	
	scanf("%d %d", &n, &m);
	for (i=1;i<=m;++i)
	{
		scanf("%d %d %d", &x[i], &y[i], &c[i]);
		
		ind[i]=i;
	}
	
	
	for (i=1;i<=n;++i)
		 tata[i]=i;
	
	sort(ind+1,ind+m+1,cmp);
	
	for (i=1;i<=m;++i)
	{
		t1=find(x[ind[i]]);
		t2=find(y[ind[i]]);
		
		if (t1!=t2)
		{
			unite(t1,t2);
			cost+=c[ind[i]];
			sol[++nr]=ind[i];
		}
	}
	
	printf("%d\n", cost);
	printf("%d\n", n-1);
	for (i=1;i<=nr;++i)
		 printf("%d %d\n", x[sol[i]],y[sol[i]]);
	
	fclose(stdin);
	fclose(stdout);
	
	return 0;
	
}