#include <cstdio>
#include <vector>
#include <algorithm>

using namespace std;

const int MAX_N = 200000;
const int MAX_M = 200000;

struct Muchie{
  int u, v, cost;
  bool operator < (const Muchie &other) const{
    return cost < other.cost;
  }
};

int t[MAX_N + 5], h[MAX_N + 5];
Muchie Muchii[MAX_M + 5];
vector<Muchie>sol;

void myUnion(int x, int y){
  if (h[x] > h[y]){
    h[y] = h[x];
    t[y] = x;
  }else if (h[x] < h[y]){
    h[x] = h[y];
    t[x] = y;
  }else{
    h[x]++;
    h[y]++;
    t[y] = x;
  }
}

int myFind(int x){
  while (t[x] != x)
    x = t[x];
  return x;
}

int main(){
  freopen("apm.in", "r", stdin);
  freopen("apm.out", "w", stdout);

  int N, M;

  scanf("%d%d", &N, &M);

  for (int i = 1; i <= M; ++i)
    scanf("%d%d%d", &Muchii[i].u, &Muchii[i].v, &Muchii[i].cost);

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

  sort(Muchii + 1, Muchii + M + 1);

  int c = 0;

  for (int i = 1; i <= M; ++i){
    int U = myFind(Muchii[i].u);
    int V = myFind(Muchii[i].v);
    if (U != V){
      c += Muchii[i].cost;
      myUnion(U, V);
      sol.push_back(Muchii[i]);
    }
  }

  printf("%d\n%d\n", c, N - 1);
  for (auto it:sol)
    printf("%d %d\n", it.u, it.v);

  return 0;
}