#include <bits/stdc++.h>
using namespace std;
const int NMAX = 2e5+2;
using Edge = tuple<int, int, int>;
using pii = pair<int, int>;
int n,m;
vector<Edge> edges;

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

struct DSU {
  int n;
  vector<int> t, sz;
  DSU(){}
  DSU(int _n){
    n = _n;
    sz.resize(n+1, 1);
    t.resize(n+1);
    for(int i = 1; i <= n; i++){
      t[i] = i;
    }
  }
  int get_root(int nod){
    if(t[nod] == nod){
      return nod;
    }
    return t[nod] = get_root(t[nod]);
  }
  bool areJoined(int x, int y){
    return get_root(x) == get_root(y);
  }
  void join(int x, int y){
    if(areJoined(x, y)){
      return ;
    }
    x = get_root(x);
    y = get_root(y);
    if(sz[x] < sz[y]){
      swap(x, y);
    }
    sz[x] += sz[y];
    t[y] = x;
  }
};

int main() {
  fin >> n >> m;
  for(int i = 1; i <= m; i++){
    int x, y, z;
    fin >> x >> y >> z;
    edges.push_back({z, x, y});
  }
  sort(edges.begin(), edges.end());
  DSU dsu(n);
  int sum = 0;
  vector<pii> ans;
  for(auto [cost, x, y]: edges){
    if(!dsu.areJoined(x, y)){
      sum += cost;
      dsu.join(x, y);
      ans.emplace_back(x, y);
    }
  }
  fout << sum << "\n" << ans.size() << "\n";
  for(auto [x, y]: ans){
    fout << x << " " << y << "\n";
  }
  return 0;
}