#include <bits/stdc++.h>
#define NMAX 400010
using namespace std;

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

int t[NMAX],r[NMAX],n,m;
muchie A[NMAX];
vector <pair <int,int> > S;

void Union(int x,int y){
	if(r[x]>r[y]){
		t[y]=x;
	}else if(r[x]<r[y]){
		t[x]=y;
	}else if(r[x]==r[y]){
		t[x]=y;
		r[y]++;
	}
}

int Find(int x){
	while(t[x]!=x){
		int tata=t[x];
		x=t[x];
		t[x]=t[tata];
	}
	return x;
}

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

int main(){
	ifstream cin("apm.in");
	ofstream cout("apm.out");
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		t[i]=i;
		r[i]=1;
	}
	for(int i=0;i<m;i++){
		int x,y,c;
		cin>>x>>y>>c;
		A[i].x=x;
		A[i].y=y;
		A[i].c=c;
	}
	sort(A,A+m,cmp);
	int total=0;
	for(int i=0;i<m;i++){
		int tx=Find(A[i].x),ty=Find(A[i].y);
		if(tx!=ty){
			Union(tx,ty);
			S.push_back({A[i].x,A[i].y});
			total+=A[i].c;
		}
	}
	cout<<total<<'\n';
	cout<<S.size()<<'\n';
	for(int i=0;i<S.size();i++){
		cout<<S[i].first<<' '<<S[i].second<<'\n';
	}
	return 0;
}