#include<iostream>
#include<vector>
#include<utility>
#include<algorithm>
using namespace std;

vector< pair< int, pair<int, int> > > edges;
vector< pair<int, int> > answer;
int p[200001], size[200001];
int n, m, cost;

int parent(int x) {
	int par, t;
	par = t = x;
	while(par != p[par]) {
		par = p[par];
	}
	while(x != p[x]) {
		t = p[x];
		p[x] = par;
		x = t;
	}
	return par;
}

void uni(int px, int py) {
	if(size[px] < size[py]) p[px] = py;
	if(size[px] > size[py]) p[py] = px;
	if(size[px] == size[py]) {
		p[px] = py;
		size[py]++;
	}
}

int main() {
	freopen("apm.in", "r", stdin);
	freopen("apm.out", "w", stdout);
	int x, y, c, i, px, py;
	cin >> n >> m;
	for(i = 0; i < m; i++) {
		cin >> x >> y >> c;
		edges.push_back(make_pair(c, make_pair(x-1, y-1)));
	}
	for(i = 0; i < n; i++) {
		p[i] = i;
		size[i] = 1;
	}
	sort(edges.begin(), edges.end());
	for(i = 0; i < m; i++) {
		x = edges[i].second.first;
		y = edges[i].second.second;
		c = edges[i].first;
		px = parent(x);
		py = parent(y);
		if(px != py) {
			uni(px, py);
			cost += c;
			answer.push_back(make_pair(x, y));
		}
	}
	printf("%d\n", cost);
	printf("%d\n", answer.size());
	for(vector< pair<int, int> >::iterator it = answer.begin(); it != answer.end(); ++it) {
		printf("%d %d\n", it->first + 1, it->second + 1);
	}
	return 0;
}