#include <fstream>
#include <algorithm>
using namespace std;
ifstream fin( "apm.in" );
ofstream fout( "apm.out" );
const int MaxM = 400002;
const int MaxN = 200002;
struct graph {
  int cost, x, y;
};
int M[MaxN], ind[MaxM];
graph inG[MaxM];
graph G[MaxN];
int edges[MaxM][2];
int root( int x ) {
  if ( M[x] == x ) {
 return x;
  }
  return M[x] = root( M[x] );
}
void join( int x, int y ) {
  M[root( x )] = root( y );
}
int cmp( int a, int b ) {
  return inG[a].cost < inG[b].cost;
}
int main() {
  int n, m, i, c;
  fin >> n >> m;
  for ( i = 0; i < m; ++i ) {
 fin >> inG[i].x >> inG[i].y >> inG[i].cost;
    ind[i] = i;
 M[inG[i].x] = inG[i].x;
 M[inG[i].y] = inG[i].y;
  }
  sort( ind, ind + m, cmp );
  for ( i = 0; i < m; ++i ) {
    G[i].cost = inG[ind[i]].cost;
 G[i].x = inG[ind[i]].x;
 G[i].y = inG[ind[i]].y;
  }
  c = 0;
  int k = 0;
  for ( i = 0; i < m; ++i ) {
    if ( root( G[i].x ) != root( G[i].y ) ) {
   c += G[i].cost;
   edges[k][0] = G[i].x;
   edges[k++][1] = G[i].y;
   join( G[i].x, G[i].y );
 }
  }
  fout << c << "\n" << k << "\n";
  for ( i = 0; i < k; ++i ) {
 fout << edges[i][0] << " " << edges[i][1] << "\n";
  }
  fin.close();
  fout.close();
  return 0;
}