#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>

#define pb push_back
#define mp make_pair
#define NMax 200001

using namespace std;

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

int n, m;
vector< pair <int, pair<int, int> > > sides;
vector< pair <int, int> > sol;
int s = 0;
int F[NMax], L[NMax];

void read() {
	f>>n>>m;
	for (int i=1;i<=m;i++) {
		int x, y, c;
		f>>x>>y>>c;
		sides.pb(mp(c, mp(x, y)));
	}
	
	sort(sides.begin(), sides.end());

	f.close();
}

void init() {
	for (int i=1;i<=n;i++) {
		F[i] = i;
		L[i] = 1;
	}
}

int fatherOf(int node) {
	int e, aux;
	for (e=node;F[e]!=e;e=F[e]);
	for (;F[node]!=node;) {
		aux = F[node];
		F[node] = e;
		node = aux;
	}

	return e;
}

void merge(int x, int y) {
	x = fatherOf(x);
	y = fatherOf(y);

	if (x != y) {
		if (L[x] > L[y])
			F[y] = x;
		else if (L[x] < L[y])
			F[x] = y;
		else {
			F[y] = x;
			L[x]++;
		}
	}
}

void solve() {
	for (int i=0;i<sides.size();i++) {
		int a = sides[i].second.first;
		int b = sides[i].second.second;

		if (fatherOf(a) != fatherOf(b)) {
			s += sides[i].first;
			merge(a,b);

			sol.pb(mp(a,b));
		}
	}
}

void output() {
	g<<s<<'\n';
	g<<sol.size()<<'\n';
	for (int i=0;i<sol.size();i++)
		g<<sol[i].first<<' '<<sol[i].second<<'\n';
	g.close();
}

int main() {

	read();
	init();
	solve();
	output();

	return 0;
}