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

using namespace std;
int t[200005],h[200005];

int cautare_tata(int *t, int nod){

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


  return Nod;
}

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

int main(){
  int i, k, x, y, ct, n, m;
  pair<int, pair < int , int > > *Graf;
  ifstream f("apm.in");
  ofstream g("apm.out");
  f>>n>>m;

  Graf = new pair < int, pair < int , int > > [m + 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, cmp);

  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){
      ct = ct + Graf[i].first;
      Graf[i].first = -1001;
      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"<<n-1<<"\n";
  for(i=1; i<=m; i++){
    if(Graf[i].first == -1001){
      g<<Graf[i].second.first<<" "<<Graf[i].second.second<<"\n";
    }
  }

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