#include <bits/stdc++.h>

using namespace std;

struct UnionFind {
  vector<int> par;
  vector<int> rank;
  vector<int> size; 
  int c;

  UnionFind(int n) : par(n), rank(n, 0), size(n, 1), c(n) { for (int i = 0; i < n; i++) {
      par[i] = i;
    }
  }
  int find(int i) { 
    return (par[i] == i ? i : (par[i] = find(par[i])));
  }

  bool same(int i, int j) { 
    return find(i) == find(j); 
  }

  int get_size(int i) { 
    return size[find(i)]; 
  }

  int count() { 
    return c; 
  }

  void merge(int i, int j) {
    i = find(i), j = find(j);
    if (i == j) {
      return;
    }
    c--;
    if (rank[i] > rank[j]) {
      swap(i, j);
    }
    par[i] = j; 
    size[j] += size[i];
    if (rank[i] == rank[j]) {
      rank[j]++;
    }
  }
};

struct E {
  int u, v, weight;
  E(int u, int v, int weight) : u(u), v(v), weight(weight) {}
};

bool operator<(const E& a, const E& b) { 
  return a.weight < b.weight;
}

int kruskal(vector<E>& edges, int V) {
  sort(edges.begin(), edges.end());
  int cost = 0, count = 0;
  UnionFind uf(V);
  for (auto& e : edges) {
    if (!uf.same(e.u, e.v)) {
      cost += e.weight;
      uf.merge(e.u, e.v);
      count++;
      if (count == V - 1) {
        break;
      }
    }
  }
  return cost;
}

tuple< int, int, vector< pair<int, int> > > kruskal_extended(vector<E>& edges, int V) {
  sort(edges.begin(), edges.end());
  int cost = 0, count = 0;
  vector< pair<int, int> > ret_edges;
  UnionFind uf(V);
  for (auto& e : edges) {
    if (!uf.same(e.u, e.v)) {
      cost += e.weight;
      uf.merge(e.u, e.v);
      ret_edges.emplace_back(e.u, e.v);
      count++;
      if (count == V - 1) {
        break;
      }
    }
  }
  return make_tuple(cost, count, ret_edges);
}

int main() {
  freopen("apm.in", "r", stdin);
  freopen("apm.out", "w", stdout);
  int n, m;
  scanf("%d %d", &n, &m);
  vector<E> edges;
  for (int i = 0; i < m; i++) {
    int x, y, c;
    scanf("%d %d %d", &x, &y, &c);
    x--, y--;
    edges.emplace_back(x, y, c);
  }
  auto ret = kruskal_extended(edges, n);
  printf("%d\n%d\n", get<0>(ret), get<1>(ret));
  auto vec = get<2>(ret);
  for (auto& e : vec) {
    printf("%d %d\n", e.first + 1, e.second + 1);
  }
  return 0;
}