#include <cstdio>
#include <algorithm>

using namespace std;


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

#define Nmax 201000

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

int father(int t)
{
	if (t!=tata[t])
		tata[t]=father(tata[t]);
	return tata[t];
}


void unite(int t1, int t2)
{
	if (niv[t1]>niv[t2])
	    niv[t1]+=niv[t2],
		tata[t2]=t1;
	else
		niv[t2]+=niv[t1],
		tata[t1]=t2;
}

int cmp(int x, int y)
{
	return c[x]<c[y];
}

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