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

using namespace std;

int t[200005] , h[200005];

int cautare_tata(int *t, int nod){

  while (t[nod] != 0) {
    nod = t[nod];
  }

  return nod;
}

void creare(int u, int v){

  nod1 = cautare_tata(t, u);
  nod2 = cautare_tata(t, v);

  if(h[u] < h[v]){
    t[u] = v;
  }else{
    t[v] = u;
  }
  if(h[u] == h[v]){
    h[b] = h[b] + 1;
  }
}

bool cmp(pair< int,pair<int,int> >  A,  pair< int,pair<int,int> >B){
  return(A.first < B.first);
}

void initializare(int u){
  t[u] = h[u] = 0;
}

int main(){
  int i, n ,m;
  pair<int, pair < int , int > > *Graf;
	pair<int, int> *Arb;

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

  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++){
    int x, y, ct;
    f>>x>>y>>ct;
    Graf[i].first = ct;
    Graf[i].second.first = x;
    Graf[i].second.second = y;
  }

  sort(Graf, Graf + m + 1);

  for(i=1; i<=n; i++){
    initializare(i);
  }

  k = 1;
  i = 1;
  while(k <= m){
    int nod1, nod2;
    nod1 = cautare_tata(t, Graf[i].second.first);
    nod2 = cautare_tata(t, Graf[i].second.second);
    if(nod1 != nod2){
      ct = ct + Graf[k].first;
      creare(Graf[i].second.first, Graf[i].second.second);
      Arb[i].first = Graf[i].second.first;
      Arb[i].second = Graf[i].second.second;
      i = i + 1;
    }
    k = k + 1;
  }

  g<<ct<<"\n";
  g<<i<<"\n";
  for(k=1; k<=i; k++){
    g<<Arb[k].first<<Arb[k].second<<"\n";
  }

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

    return 0;
}