// Copyright 2020  Nichita Radu

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

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

#include <bits/stdc++.h>

#define NMAX 200010
#define kInf (1 << 30)
using namespace std;


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

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[NMAX];
  std::priority_queue<edge, std::vector<edge>, std::greater<edge>> pq;
  std::vector<int> p;

  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[src].push_back(std::make_tuple(cost, dst));
        edges[dst].push_back(std::make_tuple(cost,src));
    }
    fin.close();
    return ;
  }

  void Prim() {
    std::vector<int> d(n + 1, kInf);
    p = std::vector<int>(n + 1, 0);
    std::vector<bool> used(n + 1, false);
    int root = 1;
    d[root] = 0;
    p[root] = 0;
    pq.push(std::make_tuple(d[root], root));

    for (int i = 1; i <= n; i++) {
        std::tuple<int, int> e;
        int node;
        do {
            e = pq.top();
            pq.pop();
            node = std::get<1>(e);
        } while (used[node]);

        cost_apm += d[node];
        used[node] = true;
        for (auto e : edges[node]) {
            int cost = std::get<0>(e);
            int neigh = std::get<1>(e);
            if (!used[neigh] && cost < d[neigh]) {
                d[neigh] = cost;
                p[neigh] = node;
                pq.push(std::make_tuple(cost, neigh));
            }
        }
    }
    
      
  }

  void get_result() {
    Prim();
  }

  void print_output() {
      std::ofstream fout("apm.out");
      fout<<cost_apm<<"\n";
      fout<<n - 1<<"\n";
      for (int i = 2; i <= n; i++) {
            fout<<i <<" " << p[i] <<"\n";
      }
      fout.close();
  }
};

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