#include <stdio.h>
#include <algorithm>
#include <cmath>
#include <cctype>
#include <cstring>
#include <vector>
#include <deque>
using namespace std;
#define Max 200001

int rad[Max],n,m;
bool viz[Max];
struct edge{ int x,y,c; }a[Max];
bool sort_type(edge a,edge b){return a.c < b.c;}

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

void apm()
{
	int s=0,k=1;
	sort(a+1,a+m+1,sort_type);
	for(int i=1;i<=n;i++) rad[i]=i;
	for(int i=1;i<n;i++)
	{
		while(tata(a[k].x)==tata(a[k].y))k++;
		rad[tata(a[k].y)]=tata(a[k].x);
		viz[k]=1;
		s+=a[k].c;
		k++;
	}
	printf("%d\n",s);
	printf("%d\n",n-1);
	for(int i=1;i<=m;i++)
		if(viz[i])printf("%d %d\n",a[i].x,a[i].y);
}

int main()
{
	int x,y,c;
	freopen("apm.in","r",stdin);
	freopen("apm.out","w",stdout);
		scanf("%d %d",&n,&m);
		for(int i=1;i<=m;i++)scanf("%d %d %d",&a[i].x,&a[i].y,&a[i].c);
		apm();
	return 0;
}