#include <fstream>
#include <vector>
#include <algorithm>
#define NMAX 400005
using namespace std;
ifstream f("apm.in");
ofstream g("apm.out");
int n,m,L[200005],l;
struct vec{
	int x,y,z;
}v[NMAX],aux[NMAX];
int cmp(struct vec a,struct vec b){
	return a.z<b.z;
}
void citire(){
	f>>n>>m;
	int i;
	for(i=1;i<=m;++i)
		f>>v[i].x>>v[i].y>>v[i].z;
}
void apm_kruskal(){
	sort(v+1,v+1+m,cmp);
	int i,ct=0,k=0,j,nr1,nr2;
	for(i=1;i<=n;++i)
		L[i]=i;
	i=1;
	while(k<n-1){
		if(L[v[i].x]!=L[v[i].y]){
			aux[++l].x=v[i].x;
			aux[l].y=v[i].y;
			++k;
			ct+=v[i].z;
			nr2=L[v[i].y];
			nr1=L[v[i].x];
			for(j=1;j<=n;++j)
				if(L[j]==nr2) L[j]=nr1;
		}
		++i;
	}
	g<<ct<<'\n'<<l<<'\n';
	for(i=1;i<=l;++i){
        g<<aux[i].x<<' '<<aux[i].y<<'\n';
	}
}
int main(){
	citire();
	apm_kruskal();
    return 0;
}