#include <iostream>
#include <fstream>

using namespace std;

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

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 initializare(){
  for(int i = 1; i <= n; i++){
    v[i] = NULL;
  }
  rez = NULL;
}

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 minim(int baza, int & min, int & dr, int & st){
  nod * parcurg = new nod;
  parcurg = v[baza];
  while(parcurg != NULL){
    if(viz[parcurg -> dr] == false && (min == -1 || min > parcurg -> cost)){
      min = parcurg -> cost;
      dr = parcurg -> dr;
      st = baza;
    }
    parcurg = parcurg -> urm;
  }
}

void prim(){
  int aux[100];
  int nrPus = 1;
  int plec = 1;
  viz[plec] = true;
  aux[1] = 1;
  while(nrPus < n){
    int stMin = -1, drMin = -1;//capetele muchiei de cost minim
    int cMin = -1;
    for(int i = 1; i <= nrPus; i++){
      minim(aux[i], cMin, drMin, stMin);
    }
    nrPus++;
    aux[nrPus] = drMin;
    viz[drMin] = true;
    suma += cMin;
    muchie * nou = new muchie;
    nou -> st = stMin;
    nou -> dr = drMin;
    nou -> urm = rez;
    rez = nou;
  }
}

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

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