#include<stdio.h>
#include<algorithm>
#define N 200000
#define M 400000
int t[N];
using namespace std;

struct muchie{
	int x,y,c;
};

bool cmp( muchie a, muchie b)
{
	if(a.c<b.c)
		return true;
	return false;
}

int radacina( int x)
{
	if(t[x] == 0)
		return x;
	int r = radacina(t[x]);
	t[x] = r;
	return r;
}


muchie v[N],w[M];

int n,m,i,rx,ry;


	
	

int main()

{
	
	freopen("apm.in","r",stdin);
	freopen("apm.out","w",stdout);
	
	scanf("%d%d",&n,&m);
	
	for(i=1;i<=m;i++)
		scanf("%d%d%d",&v[i].x,&v[i].y,&v[i].c);
	
	sort(v+1,v+m+1,cmp);
	
	int nr=0; // nr de muchii selectate
	int cost = 0;
	for(i=1;i<=m;i++)
		{
			rx = radacina(v[i].x);
			ry = radacina(v[i].y);
			if(rx == ry)
				continue;
			w[++nr] = v[i]; // am adaugat i la arborele partial
			t[rx] = ry; // am reunit muchiile
			if(nr == n-1)
				break;
		}
	for(i=1;i<=nr;i++)
		cost += w[i].c;
	printf("%d\n",cost);
	printf("%d\n",nr);
	
	for(i=1;i<=nr;i++)
		printf("%d %d\n",w[i].x,w[i].y);
	return 0;
}