#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>

using namespace std;

ifstream fin("apm.in");
ofstream fout("apm.out");
pair< int, pair<int, int> > G[400010];
int n, m,a,b,ra,rb,sol,alese;
int t[200010], S[200010];

int rad(int x) {

 while (t[x] > 0)
  x = t[x];
 return x;
}

int main()
{

 fin >> n >> m;
 for (int i = 1; i <= m; i++)
 {
  fin >> G[i].second.first;
  fin >> G[i].second.second;
  fin >> G[i].first;
 }
 sort(G + 1, G + m + 1);
 for (int i = 1; i <= n; i++)
  t[i] = -1;
 for (int i = 1; i <= m; i++) {
  a = G[i].second.first;
  b = G[i].second.second;
  ra = rad(a);
  rb = rad(b);
  if (ra != rb) {
   if (-t[ra] > -t[rb]) {

    t[ra] += t[rb];
    t[rb] = ra;
   }
   else {
    t[rb] += t[ra];
    t[ra] = rb;
   }
   sol += G[i].first;

   alese++;
   S[alese] = i;
   if (alese == n - 1)
    break;
  }
 }

 fout << sol << "\n" << n - 1 << "\n";
 for (int i = 1; i <= alese; i++)
  fout << G[S[i]].second.first << " " << G[S[i]].second.second << "\n";
 return 0;
}