#include <cstdio>
#include <memory>
#include <vector>
#include <queue>
using namespace std;

class DisjointSet{
private:
  int setSize;
  vector<int> parent, rank;
public:
  DisjointSet(int size){
    setSize = size + 1;
    parent.resize(setSize);
    rank.resize(setSize);
    for (int i = 1; i < setSize; ++i) {
      parent[i] = i;
      rank[i] = 1;
    }
  }
  int findParent(int k) {
    if (parent[k] != k)
      parent[k] = findParent(parent[k]);
    return parent[k];
  }
  void unite(int a, int b) {
    a = findParent(a);
    b = findParent(b);
    if (rank[a] == rank[b]) {
      parent[a] = b;
      ++rank[b];
      return;
    }
    if (rank[a] > rank[b])
      swap(a,b);
    parent[a] = b;
  }
};

class Solver{
private:
public:
  Solver() {
    freopen("apm.in", "r", stdin);
    freopen("apm.out", "w", stdout);
  }
  ~Solver() {
    fclose(stdin);
    fclose(stdout);
  }
  void execute() {
    int N, M;
    int x, y, cost;
    scanf("%d%d", &N, &M);
    DisjointSet dSet(N);
    priority_queue<tuple<int,int,int>> pq;
    
    for (int i = 1; i <= M; ++i) {
      scanf("%d%d%d", &x, &y, &cost);
      pq.emplace(-cost, x, y);
    }

    vector<tuple<int,int>> selectedEdges;
    int totalMinCost = 0;
    while (!pq.empty()) {
      tie(cost, x, y) = pq.top();
      cost *= -1;
      pq.pop();
      
      if (dSet.findParent(x) != dSet.findParent(y)) {
	dSet.unite(x, y);
	selectedEdges.emplace_back(x,y);
	totalMinCost += cost;
      }
    }
    printf("%d\n", totalMinCost);
    printf("%d\n", (int)selectedEdges.size());
    for (auto [x, y]: selectedEdges)
      printf("%d %d\n", x, y);
  }
};

int main() {
  unique_ptr<Solver> s = make_unique<Solver>();
  s->execute();
  return 0;
}