#include <iostream>
#include <vector>
#include <tuple>

using namespace std;

template <typename T>
using vec = vector<T>;
constexpr int INF = 1e9;

class Graph {
  vec<vec<pair<int, int>>> adj;
  vec<tuple<int, int, int>> min_edge;
  vec<int> dsu;
  int N;

  int get_root(int u) {
    int aux = u;
    while (dsu[u] >= 0)
      u = dsu[u];
    int root = u;
    u = aux;
    while (u != root) {
      aux = dsu[u];
      dsu[u] = root;
      u = aux;
    }
    return root;
  }

  void join(int u, int v) {
    int root1 = get_root(u), root2 = get_root(v);
    if (root1 == root2) return;
    if (dsu[root1] > dsu[root2]) 
      swap(root1, root2);
    dsu[root1] += dsu[root2];
    dsu[root2] = root1;
  }

public:
  struct MinimumSpanningTree {
    int total_weight;
    vec<pair<int, int>> edges;
  };

  Graph(int N) : N(N), adj(N), dsu(N), min_edge(N) {}

  void add_edge(int u, int v, int weight) {
    adj[u].emplace_back(v, weight);
    adj[v].emplace_back(u, weight);
  }

  MinimumSpanningTree minimum_spanning_tree() {
    fill(dsu.begin(), dsu.end(), -1);
    MinimumSpanningTree mst;
    mst.total_weight = 0;
    int comp_cnt = N;

    while (comp_cnt > 1) {
      for (int u = 0; u < N; ++u)
        min_edge[u] = { INF, -1, -1 };
      
      for (int u = 0; u < N; ++u) 
        for (auto[v, weight] : adj[u]) {
          int root_u = get_root(u), root_v = get_root(v);
          if (root_u == root_v) continue;
          min_edge[root_u] = min(min_edge[root_u], make_tuple(weight, u, v));
          min_edge[root_v] = min(min_edge[root_v], make_tuple(weight, u, v));
        }
    
      for (int r = 0; r < N; ++r)
        if (dsu[r] < 0) {
          auto[weight, u, v] = min_edge[r];
          if (get_root(u) != get_root(v)) {
            join(u, v);
            mst.total_weight += weight;
            mst.edges.emplace_back(u, v);
            --comp_cnt;
          }
        }

    }

    return mst;
  }
};

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

  int N, M;
  cin >> N >> M;
  Graph G(N);
  for (int i = 0; i < M; ++i) {
    int u, v, weight;
    cin >> u >> v >> weight;
    G.add_edge(u - 1, v - 1, weight);
  }
  Graph::MinimumSpanningTree mst = G.minimum_spanning_tree();
  cout << mst.total_weight << '\n' << mst.edges.size() << '\n';
  for (auto[u, v] : mst.edges)
    cout << u + 1 << ' ' << v + 1 << '\n';
  return 0;
}