#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>
#include <cstring>

const int NMAX = 2e5;
const int MMAX = 4e5;

class Edge {
public:
  int x;
  int y;
  int cost;

  Edge() = default;

  Edge(int x, int y, int cost):
    x(x), y(y), cost(cost) {};
};

int n, m;

std::vector<Edge> graph;

int ds[1 + NMAX];
int ds_height[1 + NMAX];

int min_edge[1 + NMAX];

int mst_cost;
std::vector<std::pair<int, int>> ans;

int ds_find(int a) {
  if (ds[a] == a)
    return a;

  ds[a] = ds_find(ds[a]);
  return ds[a];
}

void ds_union(int x, int y) {
  if (ds_height[x] > ds_height[y])
    std::swap(x, y);

  ds[x] = y;
  ds_height[y] += (ds_height[x] == ds_height[y]);
}

void boruvka() {
  int trees = n;

  while (trees > 1) {
    memset(min_edge, -1, sizeof(min_edge));

    for (int i = 0; i < graph.size(); ++i) {
      int set1 = ds_find(graph[i].x);
      int set2 = ds_find(graph[i].y);

      if (set1 == set2)
        continue;

      if (min_edge[set1] == -1 || graph[i].cost < graph[min_edge[set1]].cost)
        min_edge[set1] = i;
      if (min_edge[set2] == -1 || graph[i].cost < graph[min_edge[set2]].cost)
        min_edge[set2] = i;
    }

    for (int i = 1; i <= n; ++i) {
      if (min_edge[i] != -1) {
        int set1 = ds_find(graph[min_edge[i]].x);
        int set2 = ds_find(graph[min_edge[i]].y);

        if (set1 == set2)
          continue;

        mst_cost += graph[min_edge[i]].cost;
        ans.emplace_back(graph[min_edge[i]].x, graph[min_edge[i]].y);

        ds_union(set1, set2);
        --trees;
      }
    }
  }
}

int main() {
  std::ifstream in("apm.in");
  std::ofstream out("apm.out");

  in >> n >> m;

  for (int i = 1; i <= m; ++i) {
    int x, y, cost;
    in >> x >> y >> cost;

    graph.emplace_back(x, y, cost);
  }

  for (int i = 1; i <= n; ++i) {
    ds[i] = i;
    ds_height[i] = 1;
  }

  boruvka();

  out << mst_cost << '\n';
  out << n - 1 << '\n';
  for (auto& edge: ans)
    out << edge.first << " " << edge.second << '\n';

  return 0;
}