#include <bits/stdc++.h>

#define N 200005

using namespace std;
ifstream f("apm.in");
ofstream g("apm.out");
int t[N], r[N], n, m;
vector<tuple<int, int, int>> muchii;

int find(int x) {
  if(t[x] == x) {
    return x;
  }
  return t[x] = find(t[x]);
}

void unite(int x, int y) {
  if(r[x] >= r[y]) {
    r[x] += r[y];
    t[y] = x;
  } else {
    r[y] += r[x];
    t[x] = y;
  }
}

void read() {
  f>>n>>m;
  int x, y, z;
  for(int i = 1;i <= m;++i) {
    f>>x>>y>>z;
    muchii.push_back({z, x, y});
  }
}

void solve() {
  for(int i = 1;i <= n;++i) {
    r[i] = 1;
    t[i] = i;
  }
  sort(muchii.begin(), muchii.end());

  vector<pair<int, int>> result;
  int result_cost = 0;
  for(const auto& tp : muchii) {
    int cost = get<0>(tp), x = get<1>(tp), y = get<2>(tp);
    if(find(x) != find(y)) {
      result_cost += cost;
      result.push_back(make_pair(x, y));
      unite(find(x), find(y));
    }
  }

  g<<result_cost<<'\n';
  g<<result.size()<<'\n';
  for(const auto& pr : result) {
    g<<pr.first<<" "<<pr.second<<'\n';
  }
}

int main() {
  read();
  solve();  
  return 0;
}