#include <climits>
#include <fstream>
#include <iostream>
#include <queue>
#include <vector>
using namespace std;

ifstream f("apm.in");
ofstream g("apm.out");
int m, n;

struct Muchie {
  int nod = 0;
  int cost = 0;
};

vector<vector<Muchie>> listaAdiacenta;
vector<bool> inTree;
vector<int> d;
vector<int> p;

struct Compare {
  bool operator()(pair<int, int> a, pair<int, int> b) {
    return a.second > b.second;
  }
};

int main() {
  f >> n >> m;
  inTree.resize(n + 1, false);
  listaAdiacenta.resize(n + 1);
  d.resize(n + 1, INT_MAX);
  p.resize(n + 1, 0);

  for (int i = 0; i < m; i++) {
    int x, y, c;
    f >> x >> y >> c;
    listaAdiacenta[x].push_back({y, c});
    listaAdiacenta[y].push_back({x, c});
  }

  priority_queue<pair<int, int>, vector<pair<int, int>>, Compare> Q;
  d[1] = 0;

  Q.push({1, d[1]});

  while (!Q.empty()) {
    int u = Q.top().first;
    Q.pop();

    if (inTree[u])
      continue;

    inTree[u] = true;

    for (auto &edge : listaAdiacenta[u]) {
      if (!inTree[edge.nod] && edge.cost < d[edge.nod]) {
        d[edge.nod] = edge.cost;
        p[edge.nod] = u;
        Q.push({edge.nod, edge.cost});
      }
    }
  }

  int s = 0;
  for (int i = 1; i <= n; i++) {
    s += d[i];
  }
  g << s << '\n';
  g << n - 1 << '\n';

  for (int i = 2; i <= n; i++) {
    g << i << ' ' << p[i] << '\n';
  }

  return 0;
}