#include <iostream>
#include <fstream>
#include <algorithm>
 
using namespace std;
ifstream f("apm.in");
ofstream g("apm.out");
 
int cautare_tata(int *t, int nod){
 
  while (t[nod] != 0) {
    nod = t[nod];
  }
 
  return nod;
}
 
int main(){
  int i, k;
  int x, y, ct;
  pair<int, pair < int , int > > *Graf;
	pair<int, int> *Arb;
	int *t, *h;
	int n, m;
  f>>n>>m;
 
  Graf = new pair < int, pair < int , int > > [m + 1];
  Arb = new pair < int , int > [m + 1];
  t = new int [n + 1];
  h = new int [n + 1];
 
  for(i=1; i<=m; i++){
    f>>x>>y>>ct;
    Graf[i].first = ct;
    Graf[i].second.first = x;
    Graf[i].second.second = y;
  }
 
  sort(Graf, Graf + m);
 
  for(i=1; i<=n; i++){
    t[i] = 0;
    h[i] = 0;
  }
 
  k = 1;
  i = 1;
  ct = 0;
  while (k <= n - 1) {
    int nod1, nod2;
    nod1 = cautare_tata(t, Graf[i].second.first);
    nod2 = cautare_tata(t, Graf[i].second.second);
    if(nod1 != nod2){
      Arb[k].first = Graf[i].second.first;
      Arb[k].second = Graf[i].second.second;
      ct = ct + Graf[i].first;
      k = k + 1;
      if(h[nod1] > h[nod2]){
        t[nod2] = nod1;
      }else{
        t[nod1] = nod2;
        if(h[nod1] == h[nod2]){
          h[nod2] = h[nod2] + 1;
        }
      }
    }
    i = i + 1;
  }
 
  g<<ct<<"\n";
  g<<k<<"\n";
  for(i=1; i<=k; i++){
    g<<Arb[i].first<<Arb[i].second<<\n;
  }
 
  f.close();
  g.close();
 
    return 0;
}