#include <stdio.h>
#include <vector>
#include <utility>
#include <algorithm>

using namespace std;

int N, M;
const int MMAX = 400005;
const int NMAX = 200005;

int set[NMAX];

typedef pair<int, int> muchie;

typedef pair<int, muchie> c_m;

vector<c_m> muchii(MMAX);

int find(int x) {
   if (x != set[x]) {
      set[x] = find(set[x]);
   }
   return set[x];
}

void union1(int x, int y) {
   int px = find(x);
   int py = find(y);

   if (px == py) {
      return;
   }

   set[px] = py;
}

int main() {
   freopen("apm.in", "r", stdin);
   freopen("apm.out", "w", stdout);

   scanf("%d %d", &N, &M);

   for (int i = 1; i < N; ++i) {
      set[i] = i;
   }

   for(int i = 0; i < M; ++i) {
      int x,y,c;
      scanf("%d %d %d", &x, &y, &c);
      muchii[i] = make_pair(c, make_pair(x,y));
   }

   sort(muchii.begin(), muchii.end());

   vector<muchie> sol;
   int arb_cost = 0;

   for (auto top : muchii) {
      muchie m = top.second;
      int c    = top.first;

      if (find(m.first) != find(m.second)) {
         arb_cost += c;
         union1(m.first, m.second);
         sol.push_back(m);
      }
   }

   printf("%d\n%d\n", arb_cost, int(sol.size()));

   for (muchie m : sol) {
      printf("%d %d\n", m.first, m.second);
   }

   fclose(stdin);
   fclose(stdout);
   return 0;
}