#include <iostream>
#include <fstream>
#include <algorithm>

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

struct muchie{
	int in, fn;
	int ct;
};

int *arb, n , m;
pair <int,int> *Arb;

int main(){
	int i, j, k, v, w, cost;

	f>>n>>m;
	muchie gr[m + 1];
	arb = new int [n + 1];
	Arb = new pair < int , int > [m + 1];

	for(i=1; i<=m; i++){
		f>>gr[i].in>>gr[i].fn>>gr[i].ct;
	}

	for(i=1; i<=n; i++){
		arb[i] = i;
	}

	muchie aux;

	for(i=1; i<m; i++){
		for(j=i+1; j<=m; j++){
			if(gr[i].ct > gr[j].ct){
				aux = gr[i];
				gr[i] = gr[j];
				gr[j] = aux;
			}
		}
	}

	k = 1;
	i = 1;
	cost = 0;
	while(k <= n-1){
		if(arb[gr[i].in] != arb[gr[i].fn]){
			cost = cost + gr[i].ct;
			k = k + 1;
			Arb[k].first = gr[i].in;
			Arb[k].second = gr[i].fn;
			w = arb[gr[i].in];
			v = arb[gr[i].fn];
			for(j=1; j<=n; j++){
				if(arb[j] == w) arb[j] = v;
			}
		}
		i = i + 1;
	}
	g<<cost<<endl;
  g<<k<<endl;
  for(i=1; i<=k; i++){
    g<<Arb[i].first<<Arb[i].second<<endl;
  }

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