#include <fstream>
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

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

struct cell{long x,y,c;}a[400001];
long r1,r2,n,m,i,j,viz[400001],rs;
vector< int > sol;

long cmp(const cell x,const cell y){return (x.c<y.c);}

long rad(long x){return (viz[x]?viz[x]=rad(viz[x]):x);}

int main(){
	
	fi >> n >> m;
	for (i=0; i<m; i++) fi >> a[i].x >> a[i].y >> a[i].c;
	
	sort(a,a+m,cmp);
	
	i=0; rs=0;
	while ((int)sol.size() < n-1){
		r1=rad(a[i].x); r2=rad(a[i].y);
		if (r1!=r2){
			sol.push_back(i);
			rs+=a[i].c;
			viz[r1]=r2;
		}
		i++;
	}
	
	fo << rs << '\n' << (n-1) << '\n';
	for (i=0; i<(int)sol.size(); i++) fo << a[sol[i]].x << ' ' << a[sol[i]].y << '\n';
	
	return 0;
}