#include <bits/stdc++.h>
#include <queue>
#include <utility>
#include <vector>
using namespace std;

#ifdef INFOARENA
ifstream fin("apm.in");
ofstream fout("apm.out");
#define cin fin
#define cout fout
#endif

struct Neighbor {
  int to;
  int cost;
};

struct Edge {
  int from;
  int to;
  int cost;
};

using Graph = vector<vector<Neighbor>>;

struct State {
  int node;
  int cost;

  bool operator>(const State& s) const {
    return cost > s.cost;
  }
};

// This is Lazy Prim with Binary Heap
pair<vector<int>, vector<int>> prim(const int n, const Graph& g) {
  vector<int> in_mst(n + 1);
  vector<int> parent_mst(n + 1);
  vector<int> cost_mst(n + 1, INT_MAX);

  // { gas, parent, to }
  using iii = tuple<int, int, int>;
  priority_queue<iii, vector<iii>, greater<iii>> pq;

  pq.push({ 0, 0, 1 });

  while (!pq.empty()) {
    auto [cost, parent, node] = pq.top();
    pq.pop();
    if (in_mst[node]) continue;

    in_mst[node] = 1;
    parent_mst[node] = parent;
    cost_mst[node] = cost;

    for (auto neigh : g[node])
      if (!in_mst[neigh.to] &&
           cost_mst[neigh.to] > neigh.cost)
          pq.push({ cost_mst[neigh.to] = neigh.cost, node, neigh.to });
  }

  return { parent_mst, cost_mst };
}

int main() {
  int n, m;
  cin >> n >> m;
  Graph g(n + 1);

  for (int i = 1; i <= m; i++) {
    int from, to, cost; cin >> from >> to >> cost;
    g[from].push_back({ to, cost });
    g[to].push_back({ from, cost });
  }

  //

  auto [parents, costs] = std::move(prim(n, g));

  int totalCost = 0;
  for (int i = 2; i <= n; i++)
    totalCost += costs[i];

  cout << totalCost << '\n';
  cout << n - 1 << '\n';
  for (int i = 2; i <= n; i++)
    cout << i << ' ' << parents[i] << '\n';
}