#include<fstream>
#include<algorithm>
#include<vector>

using namespace std;

#define Nmax 200001

int N, M, T[Nmax], L=-1, cost;
vector<pair<int, pair<int, int> > > G;
vector<pair<int, int> > sol;

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

int get_root(int x) {
	while(T[x]!=x)
		x=T[x];
	return x;
}

int main() {
	int k, i, j, c, root1, root2;
	
	f>>N>>M;
	G.resize(M); sol.resize(N-1);
	for(i=1; i<=N; i++)
		T[i]=i;
	for(k=0; k<M; k++) {
		f>>i>>j>>c;
		G[k].first=c; G[k].second.first=i; G[k].second.second=j;
	}
	sort(G.begin(),G.end());
	for(k=0; k<M; k++) {
		c=G[k].first;
		i=G[k].second.first;
		j=G[k].second.second;
		root1=get_root(i);
		root2=get_root(j);
		if(root1==root2)
			continue;
		if(root1>root2)
			T[root1]=T[root2];
		else
			T[root2]=T[root1];
		cost+=c; L++;
		sol[L].first=i; sol[L].second=j;
	}
	g<<cost<<" "<<"\n"<<N-1<<"\n";
	for(i=0; i<(int)sol.size(); i++)
		g<<sol[i].first<<" "<<sol[i].second<<"\n";

	f.close();
	g.close();
	
	return 0;
}