#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>
using namespace std;
const int NMAX = 2e5;
const int MMAX = 4e5;

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

struct hatz{
  int a, b, cost;
};
hatz edges[MMAX+1];
vector <pair<int,int>> muchii;

bool cmp( hatz x, hatz y ) {
  return x.cost < y.cost;
}
int father[NMAX+1];

int findd( int x );
void unite( int x, int y ) {
  int xx = findd( x );
  int yy = findd( y );
  if( xx != yy )
    father[xx] = yy;
}

int findd( int x ) {
  if( x == father[x] )
    return x;
  return father[x] = findd( father[x] );
}
int main() {
  int n, m, i, cost;
  fin >> n >> m;
  for( i = 0; i < m; i++ )
    fin >> edges[i].a >> edges[i].b >> edges[i].cost;
  sort( edges, edges + m, cmp );
  for( i = 1; i <= n; i++ )
    father[i] = i;
  cost = 0;
  for( i = 0; i < m; i++ ) {
    if( findd( edges[i].a ) != findd( edges[i].b ) ) {
      unite( edges[i].a, edges[i].b );
      cost += edges[i].cost;
      muchii.push_back( { edges[i].a, edges[i].b } );
    }
  }
  fout << cost << "\n" << muchii.size() << "\n";
  for( auto it: muchii )
    fout << it.first << " " << it.second << "\n";
  return 0;
}