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

ifstream cin("apm.in");
ofstream cout("apm.out");
 
struct muchie{
	int x, y, c;
} G[200001];
 
int t[200001], r[200001];
 
bool compara(muchie a, muchie b){
	return a.c < b.c;
}
 
int tata(int a){
	if(t[a])
		return t[a] = tata(t[a]);
	return a;
}
 
int main(){
	int n, m, S = 0;
	vector<int> a;
	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; i <= m; i ++){
		int tx = tata(G[i].x);
		int ty = tata(G[i].y);
		if(tx != ty){
			a.push_back(i);
			S += G[i].c;
			if(r[tx] > r[ty])
				t[ty] = tx;
			else{
				t[tx] = ty;
				if(r[tx] == r[ty])
					r[ty] ++;
			}
		}
	}
	cout << S << "\n" << n - 1 << "\n";
	for(int i = 0; i < n - 1; i ++)
		cout << G[a[i]].x << " " << G[a[i]].y << "\n";
}