#include <algorithm>
#include <ctime>
#include <vector>
#include <iostream>
#include <fstream>
#include <map>
#include <set>
#include <unordered_map>

using namespace std;

const int NMAX = 1e6, MAXM = 1e6;
int p[NMAX + 1], sz[NMAX + 1];

struct muchie {
	int x, y, c;
};

muchie muchii[MAXM + 1];

bool cmp(const muchie &a, const muchie &b) {
	return a.c < b.c;
}


int find(int x) {
	while(x != p[x]) {
		x = p[x];
	}

	return x;
}

void unite(int x, int y) {
	x = find(x);
	y = find(y);

	if(sz[x] < sz[y]) {
		p[x] = y;
		sz[y] += sz[x];
	} else {
		p[y] = x;
		sz[x] += sz[y];
	}
}

int main() {
	ifstream cin("apm.in");
	ofstream cout("apm.out");

	int n, m;
	cin >> n >> m;

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


	for(int i = 0; i < m; i++) cin >> muchii[i].x >> muchii[i].y >> muchii[i].c;

	sort(muchii, muchii + m, cmp);

	int cTotal = 0;
	int nrMuchii = 0;

	vector<int> muchiiSelectate;

	for(int i = 0; i < m; i++) {
		int x = muchii[i].x, y = muchii[i].y, c = muchii[i].c;
		if(find(x) == find(y)) continue;

		unite(x, y);

		cTotal += c;
		nrMuchii++;

		muchiiSelectate.push_back(i);
	}

	cout << cTotal << endl << nrMuchii << endl;
	for(auto i : muchiiSelectate) {
		cout << muchii[i].x << " " << muchii[i].y << endl;
	}
}