#include <bits/stdc++.h>

using namespace std;

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

struct edge {
	int x;
	int y;
	int c;
	bool operator < (const edge& other) const {
		return c < other.c;
	}
};

int n, m, x, y, c, dad[200100];
edge e[400100];
vector<edge> sol;

int f(int x) {
	return (x == dad[x] ? x : dad[x] = f(dad[x]));
}

void join(int x, int y) {
	dad[f(x)] = f(y);
}

int main() {
	in >> n >> m;
	for (int i = 1; i <= m; i++) {
		in >> x >> y >> c;
		e[i] = {x, y, c};
	}
	
	for (int i = 1; i <= n; i++)
		dad[i] = i;
		
	int rs = 0;
	sort(e + 1, e + m + 1);
	for (int i = 1; i <= m; i++) {
		x = e[i].x;
		y = e[i].y;
		c = e[i].c;
		if (f(x) == f(y))
			continue;
		join(x, y);
		rs += c;
		sol.push_back(e[i]);
	}
	
	out << rs << '\n' << n - 1 << '\n';
	for (auto it : sol)
		out << it.x << ' ' << it.y << '\n';
	return 0;
}