// Kruskal - O(MlogM+Mlog*N)
#include <fstream>
#include <vector>
#include <algorithm>
#define Nmax 200099
#define pb push_back

using namespace std;

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

struct edge{
  int x,y,c;
  edge(int x = 0, int y = 0, int c = 0) {
    this->x = x;
    this->y = y;
    this->c = c;
  }
};

struct cmp{
  bool operator()(const edge& A, const edge& B) {
    return A.c < B.c;
  }
};

int N, M, T[Nmax], rang[Nmax], costAPM;

vector < edge > E;
vector < int > sol;

int gr(int x)
{
    int R, y;
 
    //merg in sus pe arbore pana gasesc un nod care pointeaza catre el insusi
    for (R = x; T[R] != R; R = T[R]);
 
    //aplic compresia drumurilor
    for (; T[x] != x;)
    {
        y = T[x];
        T[x] = R;
        x = y;
    }
    return R;
}
 
void reunion(const int& x, const int& y){
  /* T[gr(x)] = gr(y); */
  
  int a = gr(x), b = gr(y);
  if (rang[a] > rang[b]) {
    T[b] = T[a];
  } else {
    T[a] = T[b];
  }
  if (rang[a] == rang[b]) rang[b]++; 
}

void Kruskal() {
  sort(E.begin(), E.end(), cmp());

  for(int i = 1; i <= N; ++i) {
   T[i] = i;
  }

  for(int i = 0; i < M && (int) sol.size() != N-1; ++i) {
    if(gr(E[i].x) != gr(E[i].y)) {
      costAPM += E[i].c;
      sol.push_back(i); 
      reunion(E[i].x, E[i].y);
    }
  }

}

int main()
{
   f >> N >> M;

   for(int i = 1; i <= M; ++i) {
      int x, y, c;
      f >> x >> y >> c;
      E.pb(edge(x, y, c));
    }

   Kruskal();

   g<< costAPM << '\n';
   g<< sol.size() << '\n';
   for (vector<int>::iterator it = sol.begin(); it != sol.end(); it++) {
      g<< E[*it].x << ' ' << E[*it].y << '\n';
   }
   
   f.close();g.close();
   return 0;
}