#include <bits/stdc++.h>
using namespace std;
ifstream in("apm.in");
ofstream out("apm.out");
struct edge {
	int x;
	int y;
	int c;
};
const int lim = 2e5+4;
const int lime = 4e5+4;
vector<edge> edges;
int leank[lim];
int dim[lim];
int n,m,x,y,c;
bool mycmp(edge a, edge b) {
	return a.c < b.c;
}
int tata(int x) {
	int aux = x, cpy;
	while(x!=leank[x]) x = leank[x];
	while(aux!=leank[aux]) cpy = aux, aux = leank[aux], leank[cpy] = x;
	return x;
}
bool join(int x, int y) {
	x = tata(x);
	y = tata(y);
	if (x == y) {
		return false;
	}
	if(dim[x]<dim[y]) {
		swap(x, y);
	}
	leank[y] = x;
	dim[x] += dim[y];
	return true;
}
using pii = pair<int, int>;
vector<pii> ans;
int main() {
	in>>n>>m;
	edges.resize(m);
	for(int i=0;i<m;++i) {
		in>>x>>y>>c;
		edges[i] = {x, y, c};
	}
	for(int i=1;i<=n;++i) {
		leank[i] = i;
		dim[i] = 1;
	}
	int sum = 0;
	sort(edges.begin(), edges.end(), mycmp);
	for(edge e: edges) {
		if(join(e.x, e.y)) {
			ans.push_back(make_pair(e.x, e.y));
			sum += e.c;
		}
	}
	out<<sum<<'\n';
	out<<ans.size()<<'\n';
	for(pii p: ans) {
		out<<p.first<<' '<<p.second<<'\n';
	}
	return 0;
}