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

#define MAXN 200001

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

int n, m;
vector<pair<int, int>>apm;
vector<muchie> muchii;
int tata[MAXN];

int cost_apm;

void citire() {
	scanf("%d %d ", &n, &m);
	for(int i = 1; i <= m; i++) {
		int x, y, cost;
		scanf("%d %d %d ", &x, &y, &cost);
		//graf[x].push_back({y, cost});
		//graf[y].push_back({x, cost});
		muchii.push_back({x, y, cost});
	}
}

void init_tati() {
	for(int i = 1; i <= n; i++)
		tata[i] = i;
}

int disjoint_find(int nod) {
	if(nod == tata[nod])
		return nod;
	int t = disjoint_find(tata[nod]);
	tata[nod]=t;
	return t;
}

void disjoint_union(int x, int y) {
	tata[x] = y;
}

struct comparator {
	bool operator() (muchie x, muchie y) {
		return x.cost < y.cost;
	}
}; 

int main() {
	freopen("apm.in", "r", stdin);
	freopen("apm.out", "w", stdout);

	citire();
	init_tati();

	sort(muchii.begin(), muchii.end(), comparator());

	for(auto muchie : muchii) {

		int x = muchie.x, y = muchie.y, cost = muchie.cost;	
		int tx = disjoint_find(x);
		int ty = disjoint_find(y);

		if(tx != ty) {
			disjoint_union(tx, ty);	
			cost_apm += cost;
			apm.push_back({x, y});
		}
	}

	printf("%d\n%d\n", cost_apm, n - 1);

	for(auto muchie : apm) {
		printf("%d %d\n", muchie.first, muchie.second);
	}

	return 0;
}