#include <cstdio>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;
const int NMAX = 200505;
const int INF = 0x3f3f3f3f;
struct edge {
  int node, cost;
};
int n, m;
vector<edge> G[NMAX];
vector<int> D;
int parent[NMAX];
auto comp = [] (const edge& x, const edge& y) -> bool {
  return x.cost > y.cost;
};
priority_queue<edge, vector<edge>, decltype(comp)> Q(comp);
bool processed[NMAX];

void read() {
  scanf("%d%d", &n, &m);
  int x, y, cost;
  for (int i = 1; i <= m; i++) {
    scanf("%d%d%d", &x, &y, &cost);
    G[x].push_back({y, cost});
    G[y].push_back({x, cost});
  }
}

void solve() {
  D.assign(n + 1, INF);
  D[1] = 0;
  Q.push({1, 0});
  int totalCost = 0;
  while (!Q.empty()) {
    edge a = Q.top();
    Q.pop();
    if (processed[a.node])
      continue;

    totalCost += a.cost;
    processed[a.node] = true;
    for (auto it = G[a.node].begin(); it != G[a.node].end(); it++) {
      if (!processed[it -> node] && D[it -> node] > (it -> cost)) {
        D[it -> node] = (it -> cost);
        parent[it -> node] = a.node;
        Q.push({it -> node, D[it -> node]});
      }
    }
  }

  printf("%d\n", totalCost);
  printf("%d\n", n - 1);
  for (int i = 2; i <= n; i++) {
    printf("%d %d\n", i, parent[i]);
  }
}

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

  read();
  solve();
  return 0;
}