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

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

pair<int, pair < int , int > > *Graf;
pair<int, int> *Arb;
int *t, *h;
int n, m;

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;
  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<<endl;
  g<<k<<endl;
  for(i=1; i<=k; i++){
    g<<Arb[i].first<<Arb[i].second<<endl;
  }

  f.close();
  g.close();

	return 0;
}