#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){
  int nod1, nod2;
  nod1 = cautare_tata(t, u);
  nod2 = cautare_tata(t, v);

  if(h[nod1] < h[nod2]){
    t[nod1] = nod2;
  }else{
    t[nod2] = nod1;
  }
  if(h[nod1] == h[nod2]){
    h[nod2] = h[nod2] + 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, k, cost;
  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];

  for(i=1; i<=m; i++){
    int x, y, z;
    f>>x>>y>>z;
    Graf[i].first = z;
    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;
  cost = 0;
  while(k <= m){
    int nod1, nod2;
    nod1 = cautare_tata(t, Graf[k].second.first);
    nod2 = cautare_tata(t, Graf[k].second.second);
    if(nod1 != nod2){
      cost = cost + Graf[k].first;
      creare(Graf[k].second.first, Graf[k].second.second);
      Arb[i].first = Graf[k].second.first;
      Arb[i].second = Graf[k].second.second;
      i = i + 1;
    }
    k = k + 1;
  }

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

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

    return 0;
}