#include <fstream>
#include <algorithm>
using namespace std;
ifstream f("apm.in");
ofstream g("apm.out");
const int nmax = 200005;
int father[nmax], X[nmax], Y[nmax];
int n, m;
struct muchie{
  int a, b, cost;
};
bool comp(muchie q, muchie p){
  return q.cost < p.cost;
}

int gaseste_tatal(int x){
  if(father[x] < 0){
    return x;
  }
  int root = gaseste_tatal(father[x]);
  father[x] = root;
  return root;
}

void unite(int x, int y){
    int r_x = gaseste_tatal(x);
    int r_y = gaseste_tatal(y);
    if(father[r_x] < father[r_y]){
      swap(r_x, r_y);
    }
    father[r_y] += father[r_x];
    father[r_x] = r_y;
}
muchie l[400005];
int main(){
    f >> n >> m;
    for(int i = 1; i <= m; i++){
      f >> l[i].a >> l[i].b >> l[i].cost;
    }
    for(int i = 1; i <= n; i++){
      father[i] = -1;
    }
    int len = 0;
    int cost_minim = 0;
    sort(l + 1, l + m + 1, comp);
    for(int i = 1; i <= m; i++){
      int radx = gaseste_tatal(l[i].a);
      int rady = gaseste_tatal(l[i].b);
      if(radx != rady){
        len++;
        cost_minim += l[i].cost;
        X[len] = l[i].a;
        Y[len] = l[i].b;
        unite(l[i].a, l[i].b);
      }
    }
    g << cost_minim << '\n' << len << '\n';
    for(int i = 1; i <= len; i++){
      g << X[i] << ' ' << Y[i] <<'\n';
    }
}