#include<stdio.h>
#include<stdlib.h>
#include<vector>
using namespace std;
struct muchie {int x,y;short int c;};
muchie a[400005];
int t[200005];
int h[200005];
vector<muchie> sol;
int comp(const void *a,const void *b){muchie *pa,*pb;pa=(muchie*)a;pb=(muchie*)b;return pa->c-pb->c;}
int find(int x)
{
	while(t[x]!=x) 
		x=t[x]; 
	return x;
}
int reunion(int x,int y)
{
	if(h[x]==h[y])
	{
		h[x]++;
		t[y]=x;
	}
	else
		if(h[x]>h[y])
			t[y]=x;
		else
			t[x]=y;
}
int main()
{
	freopen("apm.in","r",stdin);
	freopen("apm.out","w",stdout);
	int n,m,i,tx,ty;
	scanf("%d%d",&n,&m);
	for(i=1;i<=m;i++)
		scanf("%d%d%d",&a[i].x,&a[i].y,&a[i].c);
	qsort(a+1,m,sizeof(a[0]),comp);
	int cost_total=0,k=0;
	for(i=1;i<=n;i++)
		t[i]=i;
	for(i=1;i<=m;i++)
	{
		tx=find(a[i].x);
		ty=find(a[i].y);
		if(tx!=ty)
			{reunion(tx,ty);k++;cost_total+=a[i].c;sol.push_back(a[i]);}
		if(k==n-1)
			break;
	}
	printf("%d\n%d\n",cost_total,k);
	for(i=0;i<sol.size();i++)
		printf("%d %d\n",sol[i].x,sol[i].y);
	return 0;
}