#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], cnt;

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

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

void unite (int x, int y){
  x = root(x);
  y = root(y);
  t[x] = 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;
      cnt += 1;
      g[i].cost = 2e9;
      unite(g[i].x, g[i].y);
      v.push_back({g[i].y, g[i].x});
    }
  }
  fout << ans << '\n' << cnt << '\n';
  for (int i = 1; i <= m; i++){
    if (g[i].cost == 2e9){
      fout << g[i].x << " " << g[i].y << '\n';
    }
  }
}