/// prim
#include <iostream>
#include <cstdio>
#include <vector>
#include <bitset>
#include <queue>
#include <algorithm>
#define NMAX 200005
#define inf 0x3f3f3f3f
#define cost first
#define node second

using namespace std;

int n, m, costTotal;
vector<pair<int, int> > v[NMAX];
priority_queue<pair<int, pair<int, int> >, vector<pair<int, pair<int, int> > >, greater<pair<int, pair<int, int> > > > muchii;
               ///  cost      x     y
queue<pair<int, int> > sol;
bitset<NMAX> viz;

void read()
{
   int A, B, C;
   scanf("%d %d\n", &n, &m);
   for (int i=1; i<=m; ++i){
      scanf("%d %d %d\n", &A, &B, &C);
      v[A].push_back(make_pair(C, B));
      v[B].push_back(make_pair(C, A));
   }
}

void prim()
{
   vector<pair<int, int> >::iterator it;
   pair<int, pair<int, int> > x;
   viz[1] = 1;
   for (it = v[1].begin(); it != v[1].end(); ++it)
      muchii.push(make_pair((*it).cost, make_pair(1, (*it).node)));

   while (!muchii.empty()){
      x = muchii.top();
      muchii.pop();
      if (!viz[x.node.second]){
         viz[x.node.second] = 1;
         sol.push(make_pair(x.node.first, x.node.second));
         costTotal += x.cost;
         for (it = v[x.node.second].begin(); it != v[x.node.second].end(); ++it){
            muchii.push(make_pair((*it).cost, make_pair(x.node.second, (*it).node)));
         }
      }
   }

   printf("%d\n%d\n", costTotal, sol.size());
   while (!sol.empty()){
      printf("%d %d\n", sol.front().first, sol.front().second);
      sol.pop();
   }

}

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

   return 0;
}