#include <bits/stdc++.h>
using namespace std;

ifstream fin("apm.in");
ofstream fout("apm.out");

struct Edge {
  int u, v, w;
  bool operator < (const Edge& oth) const {
    return w < oth.w;
  }
};

const int N = 200000 + 5;
int t[N], n, m;
vector<Edge> e;

void setup() {
  for (int i = 1; i <= n; ++i)
    t[i] = i;
}
int Find(int x) {
  if (x == t[x])
    return x;
  return t[x] = Find(t[x]);
}
int Union(int x, int y) {
  int r1 = Find(x);
  int r2 = Find(y);
  if (r1 != r2)
    t[r1] = r2;
}

int main() {
  fin >> n >> m;
  setup();
  while (m--) {
    int u, v, w;
    fin >> u >> v >> w;
    e.push_back((Edge){u, v, w});
  }
  sort(e.begin(), e.end());
  vector<pair<int,int>> apm;
  int cost = 0;
  for (auto edge : e) {
    int u = edge.u;
    int v = edge.v;
    int w = edge.w;
    if (Find(u) != Find(v)) {
      apm.emplace_back(u, v);
      Union(u, v);
      cost += w;
    }
  }
  fout << cost << '\n';
  fout << apm.size() << '\n';
  for (auto i : apm)
    fout << i.first << ' ' << i.second << '\n';
}