#include <bits/stdc++.h>
#include <fstream>
#include <vector>
using namespace std;
ifstream fin("apm.in");
ofstream fout("apm.out");

struct DSU {
  vector<int> parent, rank;
  DSU(int x) {
    parent.resize(x + 1);
    rank.resize(x + 1, 0);
    for (int i = 0; i < parent.size(); i++)
      parent[i] = i;
  }

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

  bool unite(int x, int y) {
    x = parent[x];
    y = parent[y];
    if (parent[x] == parent[y])
      return false;
    if (rank[x] < rank[y])
      swap(x, y);
    parent[y] = parent[x];
    if (rank[x] == rank[y])
      rank[x]++;
    return true;
  }
};

int main() {
  int n, m, ans = 0;
  vector<vector<int>> edges;
  vector<pair<int, int>> output;
  fin >> n >> m;
  DSU tree(n);
  for (int i = 0; i < m; i++) {
    int x, y, w;
    fin >> x >> y >> w;
    edges.push_back({w, x, y});
  }
  sort(edges.begin(), edges.end());
  for (int i = 0; i < edges.size(); i++) {
    if (tree.unite(edges[i][1], edges[i][2])) {
      ans += edges[i][0];
      output.push_back({edges[i][1], edges[i][2]});
    }
  }
  fout << ans << "\n" << output.size() << "\n";
  for (int i = 0; i < output.size(); i++)
    fout << output[i].first << " " << output[i].second << "\n";
  return 0;
}