#include <fstream>
#include <algorithm>
using namespace std; 
 
ifstream cin("apm.in");
ofstream cout("apm.out");
 
struct muchie{
	int x, y, c;
} G[200001], A[200001];

int t[200001];
 
bool compara(muchie a, muchie b){
	return a.c < b.c;
}

int tata(int a){
	if(t[a])
		return tata(t[a]);
	return a;
}
 
int main(){
	int n, m, S = 0, cnt = 0;
	cin >> n >> m;
	for(int i = 1; i <= m; i ++)
		cin >> G[i].x >> G[i].y >> G[i].c;
	sort(G + 1, G + m + 1, compara);
	for(int i = 1; cnt < n - 1; i ++){
		int tx = tata(G[i].x);
		int ty = tata(G[i].y);
		if(tx != ty){
			t[tx] = ty;
			A[++ cnt] = G[i];
			S += G[i].c;
		}
	}
	cout << S << "\n" << cnt << "\n";
	for(int i = 1; i < n; i ++)
		cout << A[i].x << " " << A[i].y << "\n";
}