#include <bits/stdc++.h>
#define NMAX 200000
#define MMAX 400000
using namespace std;

struct Edge {
  int x;
  int y;
  int cost;
}G[MMAX];

int root[NMAX], rang[NMAX];
vector<pair<int,int>> arbore;

bool cmp( Edge a, Edge b ) {
  return a.cost < b.cost;
}

int find_root( int x ) {
  int og = x;
  while( root[og] != og )
    og = root[og];
  while( root[x] != x ) {
    int oog = root[x];
    root[x] = og;
    x = oog;
  }
  return og;
}

void unite( int x, int y ) {
  if( rang[x] > rang[y] )
    root[y] = x;
  else
    root[x] = y;
  if( rang[x] == rang[y] )
    rang[y] ++;
}

int main() {
    ifstream fin("apm.in");
    ofstream fout("apm.out");
    int n, m, i, ans;
    fin>>n>>m;
    for( i = 1; i <= m; i ++ )
      fin>>G[i].x>>G[i].y>>G[i].cost;
    for( i = 1; i <= n; i ++ )
      root[i] = i, rang[i] = 0;
    sort(G + 1, G + m + 1, cmp);
    ans = 0;
    int k = 0;
    for( i = 1; k <= n - 2; i ++ ) {
      int rootx = find_root(G[i].x);
      int rooty = find_root(G[i].y);
      if( rootx != rooty ) {
        k ++;
        ans += G[i].cost;
        unite(rootx,rooty);
        arbore.push_back({G[i].x,G[i].y});
      }
    }
    fout<<ans<<"\n"<<n-1<<"\n";
    for( auto it : arbore )
     fout<<it.first<<" "<<it.second<<"\n";
    return 0;
}