#include<bits/stdc++.h>
#define N 200020
#define M 400020
using namespace std;
struct nod{
	int x, y, c;
}a[M];
int k[N], s[N], mc[N][3];
bool cmp(nod a, nod b){
	return (a.c < b.c);
}
int find(int x){
	while (x != k[x]) x=k[x];
	return x;
}
int same(int a, int b){
	return(find(a) == find(b));
}
void unite(int a, int b){
	a=find(a);
	b=find(b);
	if(s[a]<s[b])swap(a, b);
	s[a]+=s[b];
	k[b]=a;
}
int main(){
	int t, n, m, sum=0, p=0;
	freopen("apm.in", "r", stdin);
	freopen("apm.out", "w", stdout);
		sum=0;
		scanf("%d%d", &n, &m);
		
	for(int i=1;i<=n;i++){
		k[i]=i;
		s[i]=1;
	}
	for(int i=1;i<=m;i++)scanf("%d%d%d", &a[i].x, &a[i].y, &a[i].c);
	sort(a+1, a+1+m, cmp);
	for(int i=1;i<=m;i++){
		if(!same(a[i].x, a[i].y)) {
			unite(a[i].x, a[i].y);
			sum+=a[i].c;
			mc[++p][1]=a[i].x;
			mc[p][2]=a[i].y;
		}
	}
	printf("%d\n", sum);
	printf("%d\n", p);
	for(int i=1;i<=p;i++)printf("%d %d\n", mc[i][1], mc[i][2]);
	return 0;
}