#include<fstream>
#include<vector>
#include<bitset>
#define NMAX 200005
#define MMAX 400005

struct muchie {
  int a,b,c;
};

int n,m,nr;
int cost,count = 1;
muchie h[MMAX],a[MMAX];
std::vector <int> v[NMAX],c[NMAX];
std::bitset <NMAX> viz;
std::ifstream in("apm.in");
std::ofstream out("apm.out");

void scan() {
  int a,b,cost;
  in>>n>>m;
  for (int i = 1; i <= m; ++i) {
    in>>a>>b>>cost;
    v[a].push_back(b);
    c[a].push_back(cost);
    v[b].push_back(a);
    c[b].push_back(cost);
  }
}

void addToHeap(int a,int b,int c)
{
  int k;
  int t;
  muchie aux;
  h[++nr].a = a;
  h[nr].b = b;
  h[nr].c = c;
  k = nr;
  while (k)
  {
    t = (k>>1);
    if (t && h[t].c>h[k].c) {
      aux  = h[k];
      h[k] = h[t];
      h[t] = aux;
    } else {
      break;
    }
    k=t;
  }
}

void eliminateFromHeap() {
  h[1]=h[nr];
  nr--;
  int k = 1,fs,fd;
  muchie aux;
  while (k<nr) {
    fs = (k<<1);
    fd = (k<<1) + 1;
    if (fd<=nr)
    {
      if (h[fd].c < h[fs]. c) {
        if (h[fd].c < h[k].c) {
          aux   = h[fd];
          h[fd] = h[k];
          h[k]  = aux;
          k = fd;
        } else return;
      } else {
          if (h[fs].c < h[k].c) {
            aux   = h[fs];
            h[fs] = h[k];
            h[k]  = aux;
            k = fs;
          } else return;
      }
    } else
      if (fs<=nr){
        if (h[fs].c < h[k].c) {
             aux   = h[fs];
             h[fs] = h[k];
             h[k]  = aux;
             k = fs;
           } else return;}
        else return;
  }


}
void prim() {
    int noda,nodb;
    viz.reset();
  viz[1] = true;
  for (int i = 0;i<v[1].size(); ++i) {
    addToHeap(1,v[1][i],c[1][i]);
  }
  while (count < n) {
    if (viz[h[1].a]) {
      if (viz[h[1].b] == false) {
        cost = cost + h[1].c;
        a[count] = h[1];
        ++count;
        viz[h[1].b] = true;
        noda = h[1].a;
        nodb = h[1].b;
        eliminateFromHeap();
        for (int i = 0;i<v[nodb].size(); ++i) {
          addToHeap(nodb,v[nodb][i],c[nodb][i]);
        }
      } else {
        eliminateFromHeap();
      }
    } else {
        cost = cost + h[1].c;
        a[count] = h[1];
        viz[h[1].a] = true;
        eliminateFromHeap();
        noda = h[1].a;
        nodb = h[1].b;
        for (int i = 0;i<v[noda].size(); ++i) {
          addToHeap(noda,v[noda][i],c[noda][i]);
        }
        ++count;
    }
  }
}

void print() {
  out<<cost<<"\n";
  out<<count-1<<"\n";
  for (int i = 1; i < count; ++i) {
    out<<a[i].a<<" "<<a[i].b<<"\n";
  }
}

int main() {
  scan();
  prim();
  print();
  return 0;
}