#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;
	ifstream f("apm.in");
	ofstream g("apm.out");
		sum=0;
		f>>n>>m;
		
	for(int i=1;i<=n;i++){
		k[i]=i;
		s[i]=1;
	}
	for(int i=1;i<=m;i++)f>>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;
			if(a[i].y>a[i].x) swap(a[i].x, a[i].y);
			mc[++p][1]=a[i].x;
			mc[p][2]=a[i].y;
		}
	}
	g<<sum<<endl;
	g<<p<<endl;
	for(int i=1;i<=p;i++)g<<mc[i][1]<<' '<<mc[i][2]<<endl;
	return 0;
}