#include <bits/stdc++.h>
#include <fstream>

using namespace std;

ifstream in("apm.in");
ofstream out("apm.out");

const int nmax=400005;
int n,m,k,total,tt[nmax],rg[nmax];
pair<int,int> p[nmax];

struct edge{
	int x,y,c;
}v[nmax];

bool compare(edge a,edge b){
	return a.c<b.c;
}
int find(int nod){
	while(tt[nod] !=nod){
		nod=tt[nod];
	}
	return nod;
}
int unite(int x,int y){
	if(rg[x]<rg[y]){
		tt[x]=y;
	}
	if(rg[y]<rg[x]){
		tt[y]=x;
	}
	if(rg[x]==rg[y]){
		tt[x]=y;
		rg[y]++;
	}
}

void rez(){
	for(int i=1;i<=m;i++){
		if(find(v[i].x) !=find(v[i].y)){
			unite(find(v[i].x),find(v[i].y));
			p[++k].first=v[i].x;
			p[k].second=v[i].y;
			total += v[i].c;
		}
		
	}
}

int main(){
in >>n>>m;
for(int i=1;i<=m;i++){
	in >>v[i].x>>v[i].y>>v[i].c;
}
sort(v+1, v+m+1,compare);

for(int i=1;i<=m;i++){
	tt[i]=i;
	rg[i]=1;
}
rez();
out <<total<<"\n";
out <<n-1<<"\n";

for(int i=1;i<=k;i++){
	out <<p[i].first <<" "<<p[i].second<<"\n";
}

}