#include <stdio.h>
#include <vector>
#include <algorithm>
#include <iostream>
#include <sstream>

using namespace std;


struct edge {
  int x, y, c;
  edge(int x_, int y_, int c_): x(x_), y(y_), c(c_) {
  };
  bool operator<(const edge& other) const {
    return c<other.c;
  }
  friend ostream& operator<<(ostream& os, const edge&e) {
    os << e.x << " " << e.y;
    return os;
  }
};

int n, m;
vector<edge> edges;
int parent[200000];

void init_sets() {
  for (int i=0; i<n; i++) parent[i] = i;
}

int find_set(int x) {
  if (parent[x]==x) return x;
  else {
    int par = find_set(parent[x]);
    // Path compression
    parent[x] = par;
    return par;
  }
}

void union_sets(int x, int y) {
  static int ran = 1234;
  ran = (ran*1219)%2132;
  if (ran&1) {
    parent[x] = y;
  } else {
    parent[y] = x;
  }
}

void kruskal() {
  init_sets();
  sort(edges.begin(), edges.end());
  stringstream result;
  int sum_costs = 0;
  for (int i=0; i<m; i++) {
    int x = edges[i].x, y = edges[i].y;
    int findx = find_set(x), findy = find_set(y);
    if (findx == findy) continue;
    sum_costs += edges[i].c;
    union_sets(findx, findy);
    result<<edges[i]<<endl;
  }
  cout << sum_costs << endl;
  cout << n-1 << endl;
  cout << result.str();
}

int main() {
  freopen("apm.in", "r", stdin);
  freopen("apm.out", "w", stdout);
  scanf("%d %d", &n, &m);
  for (int i=0; i<m; i++) {
    int x, y, c;
    scanf("%d %d %d", &x, &y, &c);
    edges.push_back(edge(x, y, c));
  }
  kruskal();
  return 0;
}