#include <bits/stdc++.h>

using namespace std;

const int Nmax = 200001;
typedef tuple< int, int, int> TI;

int parent[Nmax], rnk[Nmax];
bool used[2 * Nmax];
vector<TI> edges;

int find ( int u ) {
  if ( u != parent[u] )
    parent[u] = find( parent[u] );

  return parent[u];
}

void merge ( int u, int v ) {
  u = find( u );
  v = find( v );

  if ( u == v )
    return;

  if ( rnk[u] < rnk[v] )
    swap( u, v );
  parent[v] = u;
  if ( rnk[u] == rnk[v] )
    rnk[u]++;
}

int main()
{
    int n, m, cost, u, v, i, comp, ans;
    ifstream fin ( "apm.in" );
    ofstream fout ("apm.out" );

    fin >> n >> m;
    for ( i = 0; i < m; i ++ ) {
      fin >> u >> v >> cost;
      edges.push_back( make_tuple(cost, u, v ) );
    }

    for ( i = 1; i<=n ; i ++ ) {
      parent[i] = i;
      rnk[i] = 1;
    }

    sort( edges.begin(), edges.end() );
    comp = n;
    i = 0;
    while( comp > 1 ) {
      u = get<1>(edges[i]);
      v = get<2>(edges[i]);
      cost = get<0>(edges[i]);
      if ( find(u) != find(v) ) {
        comp--;
        merge( u, v);
        used[i] = true;
        ans += cost;
      }
      i++;
    }

    fout << ans << "\n" << n - 1 << "\n";
    for ( i = 0; i < edges.size(); i ++ ) {
      if ( used[i] == true )
        fout << get<1>(edges[i]) << " " << get<2>(edges[i]) << "\n";
    }

    fout.close();
    fin.close();
    return 0;
}