#include<bits/stdc++.h>
using namespace std;
ifstream fin("amp.in");
ofstream fout("amp.out");

int n, m, apm, dsu[200010];
vector<pair<int, int>> edges;

struct node {
	int x, y, c;
}G[200010];

bool compare(node x, node y) {
	return x.c < y.c;
}

int group(int x) {
	if (dsu[x] == x) {
		return x;
	}

	dsu[x] = group(dsu[x]);
	return dsu[x];
}

void unify(int i) {
	dsu[group(G[i].x)] = group(G[i].y);
}

bool same_dsu(int i) {
	return group(G[i].x) != group(G[i].y);
}

int main() {
	ios_base::sync_with_stdio(false);
	
	fin >> n >> m;
	
	for (int i = 0; i < m; ++i) {
		fin >> G[i].x >> G[i].y >> G[i].c;
	}

	for (int i = 1; i <= n; ++i) {
		dsu[i] = i;
	}

	sort(G, G + m, compare);

	for (int i = 0; i < m; ++i) {
		if (same_dsu(i)) {
			apm += G[i].c;
			unify(i);
			edges.push_back({ G[i].x, G[i].y });
		}
	}

	fout << apm << '\n' << n - 1 << '\n';
	for (auto i : edges) {
		fout << i.first << ' ' << i.second << '\n';
	}

	return 0;
}