#include <cstdio>
#include <vector>
#include <algorithm>
#include <queue>
#include <tuple>

using namespace std;

vector<pair<int,pair<int,int>>> edges;
vector<int> parent;

int findParent(int k) {
  if (parent[k] != k)
    parent[k] = findParent(parent[k]);
  return parent[k];
}

int Union(int x, int y) {
  x = findParent(x);
  y = findParent(y);
  parent[y] = x;
}

int main()
{
  freopen("apm.in", "r", stdin);
  freopen("apm.out", "w", stdout);

  int N, M;
  scanf("%d%d", &N, &M);
  parent.resize(N + 1);
  for (int i = 1; i <= N; ++i)
    parent[i] = i;

  int from, to, cost;
  for (int i = 0; i < M; ++i) {
    scanf("%d%d%d", &from, &to, &cost);
    edges.push_back({cost, {from, to}});
  }
  sort(edges.begin(), edges.end());

  int total = 0;
  vector<pair<int,int>> ans;
  for (auto it : edges) {
    cost = it.first;
    tie(from, to) = it.second;
    if (findParent(from) != findParent(to)) {
      Union(from, to);
      total += cost;
      ans.emplace_back(from, to);
    }
    
  }

  printf("%d\n%d\n", total, (int)ans.size());
  for (auto it: ans)
    printf("%d %d\n", it.first, it.second);

  return 0;
}