#include <climits>
#include <fstream>
#include <iostream>
#include <queue>
#include <vector>
using namespace std;

ifstream f("apm.in");
ofstream g("apm.out");
int m, n;

struct Muchie
{
  int nod = 0;
  int cost = 0;
};

vector<vector<Muchie>> la;
vector<bool> in_arbore;
vector<int> cost_muchie;
vector<int> tata;

// struct Compare
// {
//   bool operator()(pair<int, int> a, pair<int, int> b)
//   {
//     return a.second > b.second;
//   }
// };

bool ComparareMuchii(pair<int, int> &a, pair<int, int> &b)
{
  return a.second > b.second;
}

void Read()
{
  f >> n >> m;
  in_arbore.resize(n + 1, false);
  la.resize(n + 1);
  cost_muchie.resize(n + 1, INT_MAX);
  tata.resize(n + 1, 0);

  for (int i = 0; i < m; i++)
  {
    int x, y, c;
    f >> x >> y >> c;
    la[x].push_back({y, c});
    la[y].push_back({x, c});
  }
}
void Prim()
{

  // priority_queue<pair<int, int>, vector<pair<int, int>>, Compare> Q;
  priority_queue<pair<int, int>, vector<pair<int, int>>, decltype(&ComparareMuchii)> q(ComparareMuchii);
  cost_muchie[1] = 0;

  q.push({1, cost_muchie[1]});

  while (!q.empty())
  {
    int u = q.top().first;
    q.pop();

    if (in_arbore[u])
      continue;

    in_arbore[u] = true;

    for (auto &vecin : la[u])
    {
      if (!in_arbore[vecin.nod] && vecin.cost < cost_muchie[vecin.nod])
      {
        cost_muchie[vecin.nod] = vecin.cost;
        tata[vecin.nod] = u;

        q.push({vecin.nod, vecin.cost});
      }
    }
  }

  int cost_arbore = 0;
  for (int i = 1; i <= n; i++)
  {
    cost_arbore += cost_muchie[i];
  }

  g << cost_arbore << '\n';
  g << n - 1 << '\n';

  for (int i = 2; i <= n; i++)
  {
    g << i << ' ' << tata[i] << '\n';
  }
};

int main()
{
  Read();
  Prim();

  return 0;
}