#include <iostream>
#include <fstream>
#include <set>
#include <iterator>

using namespace std;

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

typedef pair < int, pair < int, int > > PII;
set <PII> muc;
set <PII> :: iterator it;

struct nod{
  int dr, cost;
  nod * urm;
}*v[200001];

struct muchie{
  int st, dr;
  muchie * urm;
}* rez;

int n, m;//date de intrare
bool viz[200001];
int suma ;

void citire(){
  in >> n >> m;
  for(int i = 1; i <= m; ++i){
    int x, y, c;
    in >> x >> y >> c;
    nod * nou1 = new nod;
    nou1 -> dr = y;
    nou1 -> cost = c;
    nou1 -> urm = v[x];
    v[x] = nou1;
    nod * nou2 = new nod;
    nou2 -> dr = x;
    nou2 -> cost = c;
    nou2 -> urm = v[y];
    v[y] = nou2;
  }
}

void prim(){
  int nrPus = 1;
  viz[1] = true;
  nod * parcurg = new nod;
  parcurg = v[1];
  while(parcurg != 0){
    muc.insert({parcurg -> cost,make_pair(1, parcurg -> dr)});
    parcurg = parcurg -> urm;
  }//ok
  // for(it = muc.begin(); it != muc.end(); it++){
  //   out << it->second.first << ' ' << it->second.second << '\n';
  // }
  while(nrPus < n){
    while(viz[muc.begin() -> second.first] == true && viz[muc.begin() -> second.second] == true){
      muc.erase(muc.begin());
    }
    int nodNou = muc.begin() -> second.second;
    suma +=  muc.begin() -> first ;
    muchie * nou = new muchie;
    nou -> st = muc.begin()->second.first;
    nou -> dr = muc.begin()->second.second;
    nou -> urm = rez;
    rez = nou;
    viz[nodNou] = true;
    parcurg = v[nodNou];
    nrPus++;
    while(parcurg != 0){
      if(viz[parcurg -> dr] == false && viz[nodNou] == true){
        muc.insert({parcurg -> cost,make_pair(nodNou, parcurg -> dr)});
      }
      parcurg = parcurg -> urm;
    }
  }
}

void afisare(){
  out << suma << '\n' << n - 1 << '\n';
  while(rez != NULL){
    out << rez -> st << ' ' << rez -> dr << '\n';
    rez = rez -> urm;
  }
}

int main(){
  citire();
  prim();
  afisare();
  return 0;
}