#include <bits/stdc++.h>
using namespace std;

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

int t[200005], sz[200005], n, m;
vector<pair<int, pair<int, int> > > e;

int root(int x) {
	if(t[x] == 0) return x;
	return t[x] = root(t[x]);
}

int merge(int x, int y) {
	x = root(x);
	y = root(y);
	if(x == y) return 0;

	if(sz[x] < sz[y]) swap(x, y);

	t[y] = x;
	sz[x] += sz[y];
	return 1;
}

int main() {
	fin >> n >> m;
	while(m--) {
		int a, b, c;
		fin >> a >> b >> c;
		e.push_back({c, {a, b}});
	}
	sort(e.begin(), e.end());

	int cost = 0;
	vector<pair<int, int> > ans;
	for(auto x : e) {
		if(merge(x.second.first, x.second.second)) {
			cost += x.first;
			ans.push_back(x.second);
		}
	}

	fout << cost << '\n' << n-1 << '\n';
	for(auto x: ans) fout << x.first << ' ' << x.second << '\n';
}