#include <iostream>
#include <vector>
#include <queue>

#define NMAX 200000

using namespace std;

struct muchie {
  int from ;
  int to ;
  int cost ;
  int pozinit ;
  bool operator < (const muchie &a ) const {
    return (cost > a.cost ) ;
  }
};

int viz [ NMAX + 1 ] ;
vector <muchie> g [ NMAX + 1 ] ;
priority_queue <muchie> q ;
vector <muchie> rasp ;

int apm (int sursa, int n) {
  int costapm, noduri ;
  for (auto elem : g[sursa])
    q.push({elem.from, elem.to, elem.cost}) ;
  viz[sursa] = 1 ;
  noduri = 1 ;
  costapm = 0 ;
  while (noduri < n) {
    muchie next = q.top() ;
    q.pop() ;
    if (viz[next.to] == 0 ) {
      noduri++;
      rasp.push_back({next.from, next.to, next.cost}) ;
      costapm += next.cost ;
      viz[next.to] = 1 ;
      for (auto elem : g[next.to] )
        q.push({next.to, elem.to, elem.cost}) ;
    }
  }
  return costapm ;
}

int main() {

  FILE *fin, *fout ;
  fin = fopen ("apm.in", "r" ) ;
  fout = fopen ("apm.out", "w" ) ;
  int n, i, m, u, v, c ;
  fscanf (fin, "%d%d", &n, &m ) ;
  for (i = 0 ; i < m ; i++ ) {
    fscanf (fin, "%d%d%d", &u, &v, &c) ;
    g[u].push_back({u, v, c}) ;
    g[v].push_back({v, u, c}) ;
  }
  fprintf (fout, "%d\n", apm(1, n) ) ;
  fprintf (fout, "%d\n", rasp.size() ) ;
  for (i = 0 ; i < rasp.size() ; i++ )
    fprintf (fout, "%d %d\n", rasp[i].from, rasp[i].to) ;
  return 0;
}