#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#define nmax 200005
#define mmax 400005
using namespace std;

int n, m, x, y, c, cost = 0, edges;
struct edge { int a, b, w; };

vector <edge> v;
int w[nmax];		//padurea
bool check[mmax];	//muchiile luate

edge attrib(int a, int b, int w) {
	edge temp;
	temp.a = a;
	temp.b = b;
	temp.w = w;
	return temp;
}

bool cmp(edge a, edge b) { return (a.w < b.w); }

int find(int x) {
	if(w[x] < 0) return x; 

	w[x] = find(w[x]);
	return w[x];
}

void join(int R, int T) {
	if(w[R] < w[T]) {
		w[R] += w[T];
		w[T] = R;
	}
	else {
		w[T] += w[R];
		w[R] = T;
	}
}

int main() {
	ifstream f("apm.in");
	ofstream g("apm.out");

	f>>n>>m;
	for(int i=1; i<=n; i++) w[i] = -1;
	for(int i=1; i<=m; i++) {
		f>>x>>y>>c;
		v.push_back(attrib(x, y, c));
	}

	sort(v.begin(), v.end(), cmp);

	for(int i=0; i<v.size(); i++) {
		x = find(v[i].a);
		y = find(v[i].b);
	
		if(x != y) {	//arbori diferiti
			check[i] = true;
			cost += v[i].w;
			edges++;
			join(x, y);
		}
	}

	g<<cost<<"\n"<<edges<<"\n";
	for(int i=0; i<v.size(); i++)
		if(check[i]) g<<v[i].a<<" "<<v[i].b<<"\n";

	return 0;
}