#include <bits/stdc++.h>

using namespace std;

const int nmax = 200010;


vector <pair <int, int> > A[nmax];
vector <pair <int, int> > apm;
set <pair <int, int> > minCost;
int t[nmax];
int d[nmax];
int viz[nmax];

ifstream f("apm.in");
ofstream g("apm.out");
int N, M;

int main()
{
  f >> N >> M;
  for (int i = 0; i < M; i++) {
    int x, y, c;
    f >> x >> y >> c;
    A[x].push_back(make_pair(y, c));
    A[y].push_back(make_pair(x, c));
  }

  for (int i = 1; i <= N; i++) d[i] = 2001;

  for (auto it : A[1]) {
    minCost.insert(make_pair(it.second, it.first));
    t[it.first] = 1;
    d[it.first] = it.second;
  }
  viz[1] = 1;
  int cost = 0;

  for (int i = 1; i < N; i++) {
    pair <int, int> p = *minCost.begin();
    cost += p.first;
    viz[p.second] = 1;
    minCost.erase(p);
    apm.push_back(make_pair(t[p.second], p.second));
    for (auto it : A[p.second]){
      if (d[it.first] > it.second && viz[it.first] == 0) {
        minCost.erase(make_pair(d[it.first], it.first));
        d[it.first] = it.second;
        t[it.first] = p.second;
        minCost.insert(make_pair(d[it.first], it.first));
      }
    }
  }

  g << cost << "\n" << N - 1 << "\n";
  for (auto it : apm)
  {
    g << it.first << " " << it.second <<"\n";
  }
  return 0;
}