#include <iostream>
#include <vector>
#include <algorithm>

#define NMAX 200000

using namespace std;

struct muchie {
  int to ;
  int from ;
  int cost ;
};

int father [ NMAX + 1 ] ;
vector <muchie> g [ NMAX + 1 ] ;
vector <muchie> vt ;
vector <int> apm ;

bool comp (muchie a, muchie b ) {
  return ( a.cost < b.cost ) ;
}

int find (int a) {
  if (father[a] != a )
    father[a] = find (father[a]) ;
  return father[a] ;
}

void join (int a, int b ) {
  father[father[a]] = find(b) ;
}

int main() {

  FILE *fin, *fout ;
  fin = fopen ("apm.in", "r" ) ;
  fout = fopen ("apm.out", "w" ) ;
  int n, m, v, w, costT, i, c, e ;
  fscanf (fin, "%d%d", &n, &m ) ;
  for (i = 0 ; i < m ; i++ ) {
    fscanf (fin, "%d%d%d", &v, &w, &c ) ;
    g[v].push_back ({v, w, c}) ;
    vt.push_back({v, w, c}) ;
  }
  sort(vt.begin(), vt.end(), comp ) ;

  for (i = 1 ; i <= n ; i++ )
    father[i] = i ;
  e = 0 ;
  costT = 0 ;
  for (i = 0 ; i < m && e < n ; i++ ) {
    if ( find(vt[i].to) != find(vt[i].from) ) {
      costT += vt[i].cost ;
      join(vt[i].to, vt[i].from) ;
      apm.push_back(i) ;
      e++;
    }
  }
  fprintf (fout, "%d\n%d\n", costT, apm.size() ) ;
  for (i = 0 ; i < apm.size() ; i++ )
    fprintf (fout, "%d %d\n", vt[apm[i]].from, vt[apm[i]].to ) ;
  return 0;
}