#include <fstream>
#include <vector>
#include <algorithm>

using namespace std;

const int mmax = 2 * 1e5;
const int nmax = 4 * 1e5;

int father[nmax + 1];

vector <pair<int, int>> ans;

struct edge {
  int x, y, c;
};

struct edge edges[mmax + 1];
inline bool operator < (struct edge a, struct edge b){
  return a.c < b.c;
}

void build (int n){
  for (int i = 1; i <= n; i++){
    father[i] = i;
  }
}

int _find (int node){
  if (father[node] == node) return node;
  return father[node] = _find (father[node]);
}

void _union (int x, int y){
  int rootx, rooty;

  rootx = _find(x);
  rooty = _find(y);

  father[rooty] = rootx;
}

int main(){

  ifstream fin ("apm.in");
  ofstream fout ("apm.out");

  int n, m;
  fin >> n >> m;

  for (int i = 0; i < m; i++)
    fin >> edges[i].x >> edges[i].y >> edges[i].c;

  build (n);
  sort (edges, edges + m);

  int apm = 0;
  for (int i = 0; i < m; i++){
    if (_find(edges[i].x) != _find(edges[i].y)){
      _union (edges[i].x, edges[i].y);
      apm += edges[i].c;
      ans.push_back({edges[i].x, edges[i].y});
    }
  }

  fout << apm << endl << ans.size() << endl;
  for (auto sol : ans){
    fout << sol.first << " " << sol.second << endl;
  }
  return 0;
}