#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
vector<Edge> prim(const int n, const Graph& g) {
  struct State {
    int from;
    int to;
    int cost;
    bool operator>(const State& s) const {
      return cost > s.cost;
    }
  };

  vector<int> visited(n + 1);
  vector<Edge> ans;
  priority_queue<State, vector<State>, greater<State>> pq;

  // Step 1: initialize with the edges starting from node `1`
  visited[1] = 1;
  for (auto neigh : g[1]) {
    pq.push({ 1, neigh.to, neigh.cost });
  }

  while (!pq.empty() && ans.size() != n - 1) {
    auto state = pq.top();
    pq.pop();

    if (visited[state.from] && visited[state.to])
      continue;
    
    ans.push_back({ state.from, state.to, state.cost });

    for (auto neigh : g[state.to])
      if (!visited[neigh.to])
        pq.push({ state.to, neigh.to, neigh.cost });
  }

  return ans;
}

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 edges = std::move(prim(n, g));

  int cost = 0;
  for (auto& e : edges) {
    cost += e.cost;
  }

  cout << cost << '\n';
  cout << edges.size() << '\n';
  for (auto& e : edges) {
    cout << e.from << ' ' << e.to << '\n';
  }
}