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

ifstream fin("apm.in");
ofstream fout("apm.out");

typedef pair <int, int> p;

const int NMAX = 200002;
const int oo = 0x3f3f3f3f;

vector <p> g[NMAX];

int n, x, y, c, m, d[NMAX], t[NMAX], cost;

bitset <NMAX> used;

struct cmp
{
 bool operator()(const p& x, const p& y) const
 {
  return x.second > y.second;
 }
};

priority_queue<p, vector<p>, cmp > q;
int main()
{
 fin >> n >> m;
 for (int i = 1; i <= m; ++i)
 {
  fin >> x >> y >> c;
  g[x].push_back({ y,c });
  g[y].push_back({ x,c });
 }
 fill(d + 2, d + n + 1, oo);

 q.push({ 1, 0 });
 used[0] = 1;

 int vn = n;

 while (vn)
 {
  x = 0;
  while (used[x])
  {
   x = q.top().first;
   q.pop();
  }
  used[x] = 1;
  cost += d[x];
  --vn;
  vector <p>::iterator it = g[x].begin(), f = g[x].end();
  for (; it != f; ++it)
   if (it->second < d[it->first] && used[it->first] == 0)
   {
    t[it->first] = x;
    d[it->first] = it->second;
    q.push({ it->first, it->second });
   }
 }

 fout << cost << "\n" << n - 1 << "\n";

 for (int i = 2; i <= n; ++i)
  fout << i << " " << t[i] << "\n";

 return 0;
}