#include <bits/stdc++.h>

using namespace std;

const int N = 2e5 + 5;
const int INF = (1 << 30);

vector<pair<int, int>> gr[N];
bool viz[N];
int d[N], pred[N];

int apm(const int n) {
  priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> pq;
  pq.push({0, 1});
  for (int i = 2; i <= n; ++i)
    d[i] = INF;
  int sum = 0;
  while (!pq.empty()) {
    auto p = pq.top();
    pq.pop();
    int nod = p.second;
    if (viz[nod])
      continue;
    viz[nod] = true;
    sum += d[nod];
    for (auto& e: gr[nod])
      if (!viz[e.first] && e.second < d[e.first]) {
        d[e.first] = e.second;
        pred[e.first] = nod;
        pq.push({e.second, e.first});
      }
  }
  return sum;
}

int main() {
  ifstream cin("apm.in");
  ofstream cout("apm.out");
  int n, m;
  cin >> n >> m;
  while (m--) {
    int x, y, c;
    cin >> x >> y >> c;
    gr[x].emplace_back(y, c);
    gr[y].emplace_back(x, c);
  }
  cin.close();
  int sum = apm(n);
  cout << sum << "\n" << n - 1 << "\n";
  for (int i = 1; i <= n; ++i)
    if (pred[i] != 0)
      cout << pred[i] << " " << i << "\n";
  cout.close();
  return 0;
}