#include<fstream>
#include<algorithm>
#define NMAx 200100
using namespace std;
int x[NMAx],y[NMAx],C[NMAx],v[NMAx],T[NMAx],APM[NMAx];
int n,m,sol,nr;

bool cmp(int a,int b) {
	return C[a]<C[b];
}
int tata(int nod) {
	if(T[nod]!=nod)
		return tata(T[nod]);
	return T[nod];
}
void citire() {
	int i;
	ifstream in("apm.in");
	in>>n>>m;
	for(i=1;i<=m;i++) {
		in>>x[i]>>y[i]>>C[i];
		T[i]=v[i]=i;
		}
	in.close();
}
void afis() {
	int i;
	ofstream out("apm.out");
	out<<sol<<'\n'<<n-1<<'\n';
	for(i=0;i<n-1;i++)
		out<<x[APM[i]]<<" "<<y[APM[i]]<<'\n';
}
int main() {
	int i;
	citire();
	sort(v+1,v+m+1,cmp);
	for(i=1;i<=m;i++)
		if(tata(x[v[i]])!=tata(y[v[i]])) {
			sol+=C[v[i]];
			T[tata(x[v[i]])]=tata(y[v[i]]);
			APM[nr++]=v[i];
			}
	afis();
	return 0;
}