#include <set>
#include <utility>
#include <vector>
#include <limits>
#include <stdio.h>

using namespace std;

const int NMAX = 200005;
const int MMAX = 400005;

typedef pair<int,int> muchie;

int N,M,C;

vector<int> Cost(NMAX, numeric_limits<int>::max());
vector<int> E(NMAX, -1);

using namespace std;

vector<pair<int,int>> G[NMAX];

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


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

   set<pair<int,int>> set_n;
   set<int> forest;
   vector<muchie> muchii;


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

      G[x].push_back(make_pair(y, c));
      G[y].push_back(make_pair(x, c));
   }


   int arb_cost = 0;

   for (int i = 1; i <= N; ++i) {
      set_n.insert(make_pair(Cost[i], i));
   }

   while (!set_n.empty()) {
      pair<int,int> p = *set_n.begin();
      set_n.erase(set_n.begin());
      int c = p.first;
      int v = p.second;
      forest.insert(v);

      if (E[v] != -1) {
         forest.insert(E[v]);
         arb_cost += c;

         muchii.push_back(make_pair(E[v], v));
      }

      for (pair<int,int> w : G[v]) {

         int w_n = w.first;
         int w_c = w.second;
         if (Cost[w_n] > w_c && forest.find(w_n) == forest.end()) {
            set_n.erase(make_pair(Cost[w_n], w_n));

            Cost[w_n] = w_c;
            E[w_n] = v;
            set_n.insert(make_pair(Cost[w_n], w_n));
         }
      }

   }

   printf("%d\n%d\n", arb_cost, (int)muchii.size());
   for (muchie m : muchii) {
      printf("%d %d\n", m.second, m.first);
   }

   fclose(stdin);
   fclose(stdout);


   return 0;
}