#include <iostream>
#include <fstream>

using namespace std;

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

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

int n, m;
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;
    muchie * deAd = new muchie;
    deAd -> st = x;
    deAd -> dr = y;
    deAd -> cost = c;
    deAd -> urm = prim;
    prim = deAd;
  }
}

int validare(int x, int y,int &dr){
  if(viz[x] == false && viz[y] == true){
    dr = y;
    return x;
  }else if(viz[x] == true && viz[y] == false){
    dr = x;
    return y;
  }
  return -1;
}

void algPrim(){
  int nrPuse = 1;
  viz[1] = true;
  while(nrPuse < n){
    muchie * parcurg = new muchie;
    parcurg = prim;
    int cMin = -1;
    int capatNouSt = -1, capDr = -1;//capetele muchiei minime
    while(parcurg != 0){
      int dr = 0;
      int temp = validare(parcurg -> st, parcurg -> dr, dr);
      if(temp != -1 && (cMin == -1 || cMin > parcurg -> cost)){
        cMin = parcurg -> cost;
        capatNouSt = temp;
        capDr = dr;
      }
      parcurg = parcurg -> urm;
    }
    viz[capatNouSt] = true;
    suma += cMin;
    nrPuse++;
    muchie * deAd = new muchie;
    deAd -> st = capatNouSt;
    deAd -> dr = capDr;
    deAd -> urm = rez;
    rez = deAd;
  }
}

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

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