#include <fstream>
#include <vector>
#include <algorithm>
using namespace std; 

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

int N, M; 
int nrm = 0, costmin = 0; 

struct Muchie {
	int x, y, cost; 
	bool viz; 
};

Muchie a[400000]; 
int t[200000]; 

void citire() {
	cin >> N >> M; 

	for (int i = 1; i <= M; i++) {
		cin >> a[i].x >> a[i].y >> a[i].cost; 
	}
};

bool cmp(Muchie a, Muchie b) {
	return a.cost < b.cost; 
}

void Union(int a, int b) {
	t[a] = b; 
} 

int Find(int x) {
	int rad = x, y; 
	while (t[rad] != 0) {
		rad = t[rad];
	}; 

	while (x != rad) {
		y = t[x];
		t[x] = rad;
		x = y;
	}; 

	return rad; 
}

void kruskal() {
	int nrcc = N; 
	sort(a + 1, a + M + 1, cmp); 

	int radx, rady;
	for (int i = 1; i <= M && nrcc > 1; i++) {
		radx = Find(a[i].x); 
		rady = Find(a[i].y); 

		if (radx != rady) {
			Union(radx, rady); 
			nrm++; 
			nrcc--; 

			costmin += a[i].cost; 
			a[i].viz = true; 
		}
	}
}

void afisare() {
	cout << costmin << '\n'; 
	cout << nrm << '\n'; 

	for (int i = 1; i <= M; i++) {
		if (a[i].viz == true) {
			cout << a[i].x << ' ' << a[i].y << '\n'; 
		}
	}
}

int main() {
	citire(); 
	kruskal(); 
	afisare(); 

	return 0;
}