#include <bits/stdc++.h>

using namespace std;

struct Edge {
  int u, v, cost;
};

const int nmax = 2e5, mmax = 4e5;
vector<pair<int, int>> g[5 + nmax];
bool vis[5 + nmax];
pair<int, int> edge[5 + nmax];

struct Compare {
  bool operator()(Edge a, Edge b) {
    return a.cost > b.cost;
  }
};

int main() {
  ifstream fin("apm.in");
  ofstream fout("apm.out");
  int n, m;
  fin >> n >> m;
  while (m--) {
    int u, v, w;
    fin >> u >> v >> w;
    g[u].emplace_back(v, w);
    g[v].emplace_back(u, w);
  }
  priority_queue<Edge, vector<Edge>, Compare> pq;
  pq.push(Edge{.u = 1, .v = 1, .cost = 0});
  long long ans = 0;
  int ptr = 0;
  while (!pq.empty()) {
    Edge now = pq.top();
    pq.pop();
    if (vis[now.v])
      continue;
    vis[now.v] = 1;
    ans += now.cost;
    edge[++ptr] = pair<int, int>{now.u, now.v};
    for (pair<int, int> newedge : g[now.v]) 
      if (!vis[newedge.first]) 
        pq.push(Edge{.u = now.v, .v = newedge.first, .cost = newedge.second});
  }
  fout << ans << '\n' << n - 1 << '\n';
  for (int i = 2; i <= n; i++)
    fout << edge[i].first << ' ' << edge[i].second << '\n';
  return 0;
}