#include <fstream>
#include <vector>
#include <algorithm>
#define NMAX 400005
using namespace std;
ifstream f("apm.in");
ofstream g("apm.out");
int n,m,L[200005],l,X[NMAX],Y[NMAX],Z[NMAX],IND[NMAX];
vector<int> vans;
void citire(){
	f>>n>>m;
	int i;
	for(i=1;i<=m;++i){
        f>>X[i]>>Y[i]>>Z[i];
        IND[i]=i;
	}
}
int cmp(int a,int b){
    return Z[a]<Z[b];
}
void apm_kruskal(){
	sort(IND+1,IND+1+m,cmp);
	int i,ct=0,k=0,j,nr1,nr2;
	for(i=1;i<=n;++i)
		L[i]=i;
	i=1;
	while(k<n-1&&i<=m){
		if(L[X[IND[i]]]!=L[Y[IND[i]]]){
			vans.push_back(IND[i]);
			++k;
            ct+=Z[IND[i]];
			nr2=L[Y[i]];
			nr1=L[X[i]];
			for(j=1;j<=n;++j)
				if(L[j]==nr2) L[j]=nr1;
		}
		++i;
	}
	g<<ct<<'\n'<<vans.size()<<'\n';
	for(i=0;i<vans.size();++i){
        g<<X[vans[i]]<<' '<<Y[vans[i]]<<'\n';
	}
}
int main(){
	citire();
	apm_kruskal();
    return 0;
}