#include <algorithm>
#include <stdio.h>
#include <vector>

const int MAX_M = 400000;

struct Edge {
  int u;
  int v;
  int c;
  bool operator <(const Edge& other) const {
    return this->c < other.c;
  }
};
Edge edges[1 + MAX_M];
int root[1 + MAX_M];

int get_root(int i) {
  if (i != root[i])
    root[i] = get_root(root[i]);
  return root[i];
}

void join(int x, int y) {
  root[get_root(x)] = get_root(y);
}

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", &edges[i].u, &edges[i].v, &edges[i].c);
  std::sort(edges + 1, edges + m + 1);
  for (int i = 1; i <= n; i++)
	root[i] = i;
  int cost = 0;
  std::vector<Edge> ans;
  for (int i = 1; i <= m; i++) {
    if (get_root(edges[i].u) != get_root(edges[i].v)) {
	  cost += edges[i].c;
	  join(edges[i].u, edges[i].v);
	  ans.push_back(edges[i]);
    }
  }
  printf("%d\n%d\n", cost, n - 1);
  for (Edge i : ans)
    printf("%d %d\n", i.u, i.v);

  fclose(stdin);
  fclose(stdout);

  return 0;
}