#include <bits/stdc++.h>

using namespace std;

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

const int MAXM = 4e5 + 1;
const int MAXN = 2e5 + 1;

struct Edge {
  int u, v, c;
} e[MAXM];

int fth[MAXN], sz[MAXN];

int root( int u ) {
  if ( fth[u] == u ) return u;
  return fth[u] = root(fth[u]);
}
void join( int u, int v ) {
  u = root(u), v = root(v);
  if ( sz[u] > sz[v] ) swap(u, v);
  fth[u] = v;
  sz[v] += sz[u];
}

int main() {
  ios_base::sync_with_stdio(0);
  fin.tie(0);
  int n, m, res = 0;

  fin >> n >> m;
  for ( int i = 1; i <= m; ++i ) {
	fin >> e[i].u >> e[i].v >> e[i].c;
  }
  for ( int i = 1; i <= n; ++i ) {
	fth[i] = i;
	sz[i] = 1;
  }
  sort(e + 1, e + m + 1, []( const Edge &a, const Edge &b ) {
 	return a.c < b.c;
  });
  vector<pair<int, int>> sol;
  for ( int i = 1; i <= m; ++i ) {
	if ( root(e[i].u) != root(e[i].v) ) {
	  sol.push_back({e[i].u, e[i].v});
	  res += e[i].c;
	  join(e[i].u, e[i].v);
	}
  }
  fout << res << "\n" << sol.size() << "\n";
  for ( auto [u, v] : sol ) {
	fout << u << " " << v << "\n";
  }
  fin.close();
  fout.close();
  return 0;
}