#include <bits/stdc++.h>

using namespace std;

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

const int NMAX = 2e5;
const int MMAX = 4e5;

struct muchii{
  int nodx, nody, cost;
  bool operator < (const muchii &shit) const {
    return cost < shit.cost;
  }
};

vector <muchii> v;
vector <pair<int, int>> ans;

int sef[NMAX + 2];
int rang[NMAX + 2];

int myfind( int x ){
  if( sef[x] == x )
    return x;
  return sef[x] = myfind(sef[x]);
}

void myunion( int x, int y ) {
  int sefx = myfind(x), sefy = myfind(y);
  if( rang[sefx] > rang[sefy] ){
    sef[sefy] = sefx;
    rang[sefy] += rang[sefx];
  }
  else {
    sef[sefx] = sefy;
    rang[sefx] += rang[sefy];
  }
}

int main() {
  int n, m, i, x, y, z, sum;
  fin >> n >> m;
  for( i = 0; i < m; ++i ) {
    fin >> x >> y >> z;
    v.push_back({x, y, z});
  }

  for( i = 1; i <= n; ++i ) {
    sef[i] = i;
    rang[i] = 1;
  }

  sort(v.begin(), v.end());

  sum = 0;
  for( i = 0; i < v.size(); ++i ) {
    if( myfind(v[i].nodx) != myfind(v[i].nody) ){
      myunion(v[i].nodx, v[i].nody);
      sum += v[i].cost;
      ans.push_back({v[i].nodx, v[i].nody});
    }
  }

  fout << sum << "\n";
  fout << ans.size() << "\n";
  for( auto results : ans )
    fout << results.first << " " << results.second << "\n";
  return 0;
}