#include <bits/stdc++.h>

using namespace std;

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

const int NM = 4e5 + 5;

struct arb{
  int x, y, cost;
}g[NM];

long long ans = 0;
int n, m, t[NM], c[NM];

bool cmp (arb a, arb b){
  if (a.cost < b.cost){
    return true;
  }
  return (a.x < b.x);
}

int root (int x){
  if (x == t[x]){
    return x;
  }
  return t[x] = root(t[x]);
}

void unite (int x, int y){
  if (c[x] > c[y]){
    t[y] = x;
    c[y] += c[x];
  }
  else{
    t[x] = y;
    c[x] += c[y];
  }
}

int main(){
  fin >> n >> m;
  for (int i = 1; i <= m; i++){
    fin >> g[i].x >> g[i].y >> g[i].cost;
  }
  sort(g + 1, g + m + 1, cmp);
  for (int i = 1; i <= n; i++){
    t[i] = i;
    c[i] = 1;
  }

  vector<pair<int, int>>v;
  for (int i = 1; i <= m; i++){
    if (!(root(g[i].x) == root(g[i].y))){
      ans += g[i].cost;
      unite(g[i].x, g[i].y);
      v.push_back({g[i].y, g[i].x});
    }
  }
  fout << ans << '\n';
  fout << (int)v.size() << '\n';
  for (pair<int, int> x : v){
    fout << x.first << " " << x.second << '\n';
  }
}