#include <bits/stdc++.h>

using namespace std;

const int nmax = 2e5, mmax = 4e5;
int par[5 + nmax], card[5 + nmax], minedge[5 + nmax];
bool used[5 + mmax];

struct Edge {
  int u, v, cost;
} edge[5 + mmax];

int root(int u) {
  if (u == par[u])
    return u;
  return par[u] = root(par[u]);
}

void unite(int u, int v) {
  u = root(u);
  v = root(v);
  if (card[u] < card[v])
    swap(u, v);
  card[u] += card[v];
  par[v] = u;
}

int main() {
  ifstream fin("apm.in");
  ofstream fout("apm.out");
  int n, m;
  fin >> n >> m;
  for (int i = 1; i <= m; i++)
    fin >> edge[i].u >> edge[i].v >> edge[i].cost;
  int cnt = n;
  for (int i = 1; i <= n; i++) {
    par[i] = i;
    card[i] = 1;
    minedge[i] = -1;
  }
  long long ans = 0;
  while (cnt > 1) {
    for (int i = 1; i <= m; i++) {
      if (used[i])
        continue;
      int u = root(edge[i].u), v = root(edge[i].v);
      if (u != v) {
        if (minedge[u] == -1 || edge[minedge[u]].cost > edge[i].cost)
          minedge[u] = i;
        if (minedge[v] == -1 || edge[minedge[v]].cost > edge[i].cost)
          minedge[v] = i;
      }
    }
    for (int i = 1; i <= n; i++) 
      if (minedge[i] != -1) {
        int u = root(edge[minedge[i]].u), v = root(edge[minedge[i]].v);
        if (u != v) {
          ans += edge[minedge[i]].cost;
          unite(u, v);
          cnt--;
          used[minedge[i]] = 1;
        }
        minedge[i] = -1;
      }
  }
  fout << ans << '\n' << n - 1 << '\n';
  for (int i = 1; i <= m; i++)
    if (used[i])
      fout << edge[i].u << ' ' << edge[i].v << '\n'; 
  return 0;
}