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

using namespace std;

const int maxM = 4000001;

class Muchie {
public:
  int x, y, cost;
  inline bool operator < (const Muchie& other) const {
    return cost < other.cost;
  }
} G[maxM];

int padure[maxM];
int grupa(int i) {
  if(padure[i] == i)
    return i;
  padure[i] = grupa(padure[i]); /// compresia caii
  return padure[i];
}

int reuniune(int i, int j) {
  padure[grupa(i)] = grupa(j);
}

int v[maxM];

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", &G[i].x, &G[i].y, &G[i].cost);

  sort(G + 1, G + M + 1);
  for(int i = 1; i <= N; ++ i)
    padure[i] = i;

  int ans = 0;
  vector<int> v;
  for(int i = 1; i <= M; ++ i) {
    if(grupa(G[i].x) != grupa(G[i].y)) {
      ans += G[i].cost;
      reuniune(G[i].x, G[i].y);
      v.push_back(i);
    }
  }


  printf("%d\n%d\n", ans, N - 1);
  for(int i = 0; i < N - 1; ++ i)
    printf("%d %d\n", G[v[i]].y, G[v[i]].x);
  return 0;
}