#include <iostream>
	#include <algorithm>
	#include <fstream>
	#include <vector>
	using namespace std;
	int n, m, p[200005], sz[200005];
	struct edge {
		int x, y, c;
	}v[400005],rez2[200005];
	bool cmp(edge x, edge y) {
		return x.c < y.c;
	}
	int get_parent(int nod) {
		int cpy = nod;
		while (p[cpy] != 0) {
			cpy = p[cpy];
		}
		while (p[nod] != 0) {
			int cpy2 = p[nod];
			p[nod] = cpy;
			nod = cpy2;
		}
		return cpy;
	}
	void unite(int x, int y) {
		x = get_parent(x);
		y = get_parent(y);
		if (x == y) return;
		if (sz[x] < sz[y]) {
			p[x] = y;
			sz[y] += sz[x];
		}
		else {
			p[y] = x;
			sz[x] += sz[y];
		}
	}
	ifstream fin("apm.in");
	ofstream fout("apm.out");
	int main() {
		fin >> n >> m;
		for (int i = 1; i <= m; i++) {
			fin >> v[i].x >> v[i].y >> v[i].c;
		}
		int rez = 0, nr = 0;
		sort(v + 1, v + m + 1, cmp);
		for (int i = 1; i <= m; i++) {
			int x = get_parent(v[i].x);
			int y = get_parent(v[i].y);
			if (x != y) {
				unite(x, y);
				rez+=v[i].c;
				nr++;
				rez2[nr] = v[i];
			}
		}
		fout << rez << "\n" << nr << "\n";
		for (int i = 1; i <= nr; i++)
			fout << rez2[i].x << " " << rez2[i].y << "\n";
	}