#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <fstream>
#include <algorithm>
using namespace std;

#define ll long long 
#define ull unsigned long long

/*------------------------------------------------------------------*/
 
ifstream f{ "apm.in" };
ofstream q{ "apm.out" };

typedef struct _EDGE
{
   int x, y, c;

   _EDGE(): x(0),y(0),c(0){}

   _EDGE(int x, int y, int c): x(x), y(y), c(c){}

}EDGE;

EDGE edges[400006];
EDGE sol[200005];
int parent[200005];
int n, m;

bool acc(const EDGE& a, const EDGE& b)
{
   return a.c < b.c;
}

inline int find(int x)
{  
   return (parent[x] == x) ? x : parent[x] = find(parent[x]);
}

int Kruskal()
{
   int all = 0;
   int idx = 0;
   int cost = 0;

   while (all < n - 1)
   {
      if(find(edges[idx].x) != find(edges[idx].y))
      {
         cost += edges[idx].c;
         sol[all] = edges[idx];
         ++all;
         parent[find(edges[idx].x)] = find(edges[idx].y);
      }
      ++idx;
   }
   return cost;
}

int main()
{
   ios_base::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
   f >> n >> m;
   int x, y, c;

   for(int i = 1; i <= n; ++i)
   {
      parent[i] = i;
   }

   for(int i = 0; i<m; ++i)
   {
      f >> x >> y >> c;
      edges[i] = EDGE(x, y, c);
   }


   sort(edges, edges + m, acc);
   int cost = Kruskal();
   q << cost << "\n" << n - 1 << "\n";
   for(int i  = 0; i < n-1; ++i)
   {
      q << sol[i].x << " " << sol[i].y << "\n";
   }

   f.close();
   q.close();
   return 0;
}