#include <fstream>
#include <vector>
#include <queue>
using namespace std;
ifstream fin( "apm.in" );
ofstream fout( "apm.out" );
const int MaxN = 200002;
vector<int> G[MaxN];
vector<int> cost[MaxN];
priority_queue<pair<int, pair<int, int>>, vector<pair<int, pair<int, int>>>, greater<pair<int, pair<int, int>>>> q;
int viz[MaxN];
int arb[MaxN][2];
void solve( int stNode ) {
  int node, ne = 0, minc = 0;
  q.push( { 0, { stNode, stNode } } );
  while ( !q.empty() ) {
 if ( !viz[q.top().second.second] ) {
      node = q.top().second.second;
   minc += q.top().first;
   arb[ne][0] = node;
   arb[ne++][1] = q.top().second.first;
   viz[node] = 1;
      for ( int i = 0; i < G[node].size(); ++i ) {
        if ( !viz[G[node][i]] ) {
       q.push( { cost[node][i], { node, G[node][i] } } );
     }
   }
 } else {
   q.pop();
 }
  }
  fout << minc << "\n" << ne - 1 << "\n";
  for ( int i = 1; i < ne; ++i ) {
    fout << arb[i][0] << " " << arb[i][1] << "\n";
  }
}
int main() {
  int n, m, i, x, y, c;
  fin >> n >> m;
  for ( i = 0; i < m; ++i ) {
    fin >> x >> y >> c;
 G[x].push_back( y );
 G[y].push_back( x );
 cost[x].push_back( c );
 cost[y].push_back( c );
  }
  solve( 1 );
  fin.close();
  fout.close();
  return 0;
}