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

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

bool cmp(Edge &a, Edge &b) { return a.w < b.w; }

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

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

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

int main() {
  int N, M, sum = 0;
  fin >> N >> M;
  vector<Edge> edges;
  vector<pair<int, int>> ans;
  DSU dsu(N + 1);

  for (int i = 0; i < M; i++) {
    int u, v, w;
    fin >> u >> v >> w;
    edges.push_back({u, v, w});
  }

  sort(edges.begin(), edges.end(), cmp);

  for (auto it : edges) {
    if (dsu.unite(it.u, it.v)) {
      sum += it.w;
      ans.push_back({it.u, it.v});
    }
  }

  fout << sum << '\n';
  fout << ans.size() << '\n';
  for (auto it : ans) {
    fout << it.first << ' ' << it.second << '\n';
  }
}