#include <bits/stdc++.h>

using namespace std;

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

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

bool cmp(edge a, edge b){
	return a.c < b.c;
}

int n, m, x, y, c, dad[200100], rs;
edge v[400100];
vector <pair <int, int> > sol;

int find(int x){
	return (dad[x] == x ? x : dad[x] = find(dad[x]));
}

void join(int x, int y){
	dad[find(x)] = find(y);
}

int main(){
	in >> n >> m;
	for(int i = 1; i <= m; i++){
		in >> x >> y >> c;
		v[i] = {x, y, c};
	}
	sort(v + 1, v + m + 1, cmp);
	for(int i = 1; i <= n; i++)
		dad[i] = i;
	for(int i = 1; i <= m; i++){
		x = find(v[i].x);
		y = find(v[i].y);
		if(x != y){
			rs += v[i].c;
			join(x, y);
			sol.push_back({v[i].x, v[i].y});
		}
	}
	out << rs << '\n' << n - 1 << '\n';
	for(auto i : sol)
		out << i.first << ' ' << i.second << '\n';
	return 0;
}