#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;

typedef struct _EDGE
{
   int x;
   int y;
   int w;
}EDGE;

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

int n, m;
vector<EDGE> graph;
vector<EDGE> sol;
int cost = 0;
int tata[200005];
int rang[200005];

void Initializare(int n, int m)
{
   graph.clear();
   for (int i = 0; i < n + 2; ++i)
   {
      tata[i] = i;
      rang[i] = 0;
   }
}

bool cmp(EDGE left, EDGE right)
{
   return left.w < right.w;
}

int Find(int x)
{
   if (x == tata[x]) return tata[x];
   tata[x] = Find(tata[x]);
   return tata[x];
}

void Union(int x, int y)
{
   int papaX, papaY;

   papaX = Find(x);
   papaY = Find(y);

   if (papaX == papaY) return;

   if (rang[papaX] <= rang[papaY])
   {
      tata[papaY] = papaX;
      if (rang[papaX] == rang[papaY]) rang[papaX]++;
   }
   else {
      tata[papaX] = papaY;
   }
}

void Kruskal(vector<EDGE>& graph)
{
   int all = 0;
   EDGE current;
   int pz = 0;

   while (all < n - 1)
   {
      current = graph[pz];
      if (Find(current.x) != Find(current.y))
      {
         all++;
         Union(current.x, current.y);
         cost += current.w;
         sol.push_back(current);
      }
      pz++;
   }
}

int main()
{
   f >> n >> m;
   Initializare(n, m);
   int x, y, w;
   EDGE k;
   while (m--)
   {
      f >> x >> y >> w;
      k.x = x; k.y = y; k.w = w;
      graph.push_back(k);
   }
   sort(graph.begin(), graph.end(), cmp);
   Kruskal(graph);

   q << cost << "\n" << sol.size()<<"\n";
   for (EDGE e : sol)
   {
      q << e.x << " " << e.y << "\n";
   }

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