// Copyright 2020  Nichita Radu

// ProblemName RO (APM) - ProblemName EN (MST)
// AlgorithmName - Complexity

// https://infoarena.ro/problema/apm

#include <bits/stdc++.h>

#define NMAX 200010
using namespace std;


using edge = std::tuple<int, int, int>;



class DisjointSet {
    std::vector<int> parent;

 public:
    DisjointSet(int n) : parent (n + 1) {
        std::iota(parent.begin(), parent.end(), 0);
    }

    int find_root(int &node) {
        if (node == parent[node]) {
            return node;
        }

        return parent[node] = find_root(parent[node]);
    }

    void reunion(int &root1, int &root2) {
        parent[find_root(root1)] = root2;
    }
    
};

class Task {
public:
  void solve() {
    read_input();
    get_result();
    print_output();
  }

private:
  // n = numar de noduri, m = numar de muchii
  int n, m, cost_apm;

  // adj[node] lista de adiacenta a nodului node
  std::vector<edge> edges;
  std::vector<edge> apm;

  void read_input() {
    std::ifstream fin("apm.in");
    fin >> n >> m;
    for (int i = 0; i < m; i++) {
        int src, dst, cost;
        fin >> src >> dst >> cost;
        edges.push_back(std::make_tuple(src,dst,cost));
    }
    fin.close();
    return ;
  }

  void Kruskal() {

    cost_apm = 0;
    DisjointSet set(n + 1);
    apm.clear();

    for (auto e : edges) {
        int x = std::get<0>(e);
        int y = std::get<1>(e);
        int c = std::get<2>(e);
        if (set.find_root(x) != set.find_root(y)) {
            cost_apm = cost_apm + c;
            apm.push_back(e);
            set.reunion(x, y);
        }
    }
  }

  void get_result() {
      std::sort(edges.begin(), edges.end(), [](auto const &t1, auto const &t2) {
          return std::get<2>(t1) < std::get<2>(t2);
      });

      Kruskal();
  }

  void print_output() {
      std::ofstream fout("apm.out");
      fout<<cost_apm<<"\n";
      fout<<apm.size()<<"\n";
      for (auto const &e : edges) {
        fout<<std::get<0>(e) <<" " << std::get<1>(e) << "\n";
      }
      fout.close();
  }
};

int main() {
  // aici este rezolvarea propriu-zisa
  Task *task = new Task();
  task->solve();
  delete task;
  return 0;
}