#include <bits/stdc++.h>
#define L 200005
#define INF 1000000001
using namespace std;
ifstream fin("apm.in");
ofstream fout("apm.out");

int n, m;
vector <pair <int, int>> G[L];
pair <int, int> d[L];
int t[L], totalCost;
bool inAPM[L];

void prim(int root) {
  for (int i = 1; i <= n; i++)
    d[i] = {INF, 1};
  inAPM[root] = true;
  for (auto it : G[root])
    d[it.first] = {it.second, 1};
  for (int j = 2; j <= n; j++) {
    int minCost = INF, node = 0;
    for (int i = 1; i <= n; i++)
      if (!inAPM[i] && d[i].first < minCost) {
        minCost = d[i].first;
        node = i;
      }
    inAPM[node] = true;
    totalCost += minCost;
    t[node] = d[node].second;
    for (auto it : G[node])
      if (!inAPM[it.first] && d[it.first].first > it.second)
        d[it.first] = {it.second, node};
  }
}

int main() {
  fin >> n >> m;
  for (int i = 1; i <= m; i++) {
    int a, b, c;
    fin >> a >> b >> c;
    G[a].push_back({b, c});
    G[b].push_back({a, c});
  }
  prim(1);
  fout << totalCost << "\n" << n - 1 << "\n";
  for (int i = 2; i <= n; i++)
    fout << i << " " << t[i] << "\n";
  fout << "\n";
  return 0;
}