#include<fstream>
#include<vector>
#include<algorithm>
#include<utility>
#define MAXN 200005
#define pb push_back
#define INF 10000
using namespace std;
ifstream cin("apm.in");
ofstream cout("apm.out");
int N,M;
vector<int> G[MAXN],C[MAXN];
int APM[MAXN];
vector< pair<int,int> > Muchie;
int dist,k;
long long Cost=0;
int main(){
int i,j,a,b,c,u,v;
cin>>N>>M;
	for(i=1;i<=M;i++){
		cin>>a>>b>>c;
		G[a].pb(b);
		C[a].pb(c);
		G[b].pb(a);
		C[b].pb(c);
	}
	APM[1]=1;
	k++;
	dist=INF;
	while(k<N){
		dist=INF;
		for(i=1;i<=N;i++){
		if(APM[i]!=0){
			for(j=0;j<G[i].size();j++)
				if(C[i][j]<dist && (APM[G[i][j]]==0)){
					dist=C[i][j];
					u=i;
					v=G[i][j];
				}
		}
		}
		APM[v]=1;
		k++;
		Cost+=dist;
		Muchie.pb(make_pair(u,v));
	}
	cout<<Cost<<"\n";
	cout<<N-1<<"\n";
	for(i=0;i<Muchie.size();i++)
		cout<<Muchie[i].first<<" "<<Muchie[i].second<<"\n";
return 0;
}