#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <cmath>

#define For(i, x, y) for(int i = x; i <= y; ++i)
#define Forr(i, x, y) for(int i = x; i <= y; --i)
#define sz() size()
#define nMax 200005

using namespace std;
typedef struct{
  int x, y, cost;
} muchie;
typedef struct {
  int x, y;
} result;

muchie Ed;
result new_Ed;
vector <muchie> v;
vector <result> sol;
int P[nMax], h[nMax], sum, n, m;

int root(int x){
  if(P[x] != x) P[x] = root(P[x]);
  return P[x];
}
int unite(int x, int y){
  int Rx = root(x);
  int Ry = root(y);
  if(h[Rx] >= h[Ry])
    P[Ry] = Rx;
   else P[Rx] = Ry;
  if(h[Rx] == P[Ry]) h[Rx]++;
}
int cmp(muchie x, muchie y){
  return (x.cost < y.cost);
}
void apm(){
   int usedEd = 0;
   sort(v.begin(), v.end(), cmp);
   for(auto Ed : v){
    if(root(Ed.x) != root(Ed.y)){
        unite(Ed.x, Ed.y);
        usedEd++;
        sum += Ed.cost;
        new_Ed.x = Ed.x;
        new_Ed.y = Ed.y;
        sol.push_back(new_Ed);
        if(usedEd == n - 1) break;
    }
   }
}
int main()
{
    ifstream fin("apm.in");
    ofstream fout("apm.out");

    fin >> n >> m;
    For(i, 1, n){
      P[i] = i;
      h[i] = 1;
    }
    For(i, 1, m){
      fin >> Ed.x >> Ed.y >> Ed.cost;
      v.push_back(Ed);
    }
    apm();
    fout << sum << '\n' << sol.sz() << '\n';
    for(auto i: sol)
        fout << i.x << ' ' << i.y << '\n';

    return 0;
}