#include<fstream>
#include<algorithm>

using namespace std;

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


int X[200005],Y[200005],C[200005],V[200005],T[200005],APM[200005];
int N,M,sol,nr;

int cmp(int a,int b) {
	return C[a]<C[b];
}
int tata(int nod) {
	if(T[nod]!=nod) {
		T[nod]=tata(T[nod]);
		return T[nod];
		}
	return nod;
}
void citire() {
	int i;
	
	f>>N>>M;
	for(i=1;i<=M;i++) {
		f>>X[i]>>Y[i]>>C[i];
		T[i]=V[i]=i;
		}
	
}
void afis() {
	int i;
	
	g<<sol<<'\n'<<N-1<<'\n';
	for(i=0;i<N-1;i++)
		g<<Y[APM[i]]<<" "<<X[APM[i]]<<'\n';
}
int main() {
	int i,a,b;
	citire();
	sort(V+1,V+M+1,cmp);
	for(i=1;i<=M;i++) {
		a=tata(X[V[i]]);
		b=tata(Y[V[i]]);
		if(a!=b) {
			sol+=C[V[i]];
			T[a]=b;
			APM[nr++]=V[i];
			}
		}
	afis();
	return 0;
}