#include <vector>
#include <cstdio>
#include <cstring>
#include <algorithm>

#define NMAX 400100
std::vector<int> x, y, cost, ind;
int componenta[NMAX];
int n, m;

int cmp(int e1, int e2) {
	return cost[e1] < cost[e2]; 
}

void reuniune(int u, int v) {
	for (int i = 0; i < n; i++) {
		if (componenta[i] == v)
			componenta[i] = u;
	}
}

int main() {
	// read input
	// n - number of vertices in Left
	// m - number of vertices in Right
	// e - number of edges
	freopen("apm.in", "r", stdin);
	freopen("apm.out", "w", stdout);

	scanf("%d %d\n", &n, &m);
	int a, b, c;
	for (int i = 0; i < m; i++) {
		scanf("%d %d %d\n", &a, &b, &c);
		x.push_back(a - 1);
		y.push_back(b - 1);
		cost.push_back(c);
		ind.push_back(i);
	}

	std::sort(ind.begin(), ind.end(), cmp);

	for (int i = 0; i < n; i++) {
		componenta[i] = i;
	}

	int suma = 0;
	std::vector<int> muchii; 
	for (int i = 0; i < m; i++) { 
		if (componenta[x[ind[i]]] != componenta[y[ind[i]]]) {
			suma += cost[ind[i]];
			muchii.push_back(ind[i]);
			reuniune(x[ind[i]], y[ind[i]]);
		}
	}

	printf("%d\n", suma);
	printf("%lu\n", muchii.size());
	for (int i = 0; i < muchii.size(); i++) {
		printf("%d %d\n", x[muchii[i]] + 1, y[muchii[i]] + 1);
	}
	return 0;
}