#include <stdio.h>
#include <bits/stdc++.h>

#define rep(i, n) for(int i = 0; i < n; i++)
#define repa(i, l, r) for (int i = l; i < r; i++)
#define repd(i, r, l) for (int i = r; i > l; i--)

using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef array<int, 3> triple;
const int INF = 100555;
ifstream fin ("apm.in");
ofstream fout ("apm.out");
const int Nmax = 200555;
vector<pii> G[Nmax];
char vis[Nmax];

int main(void) {
  int N, M, a, b, c;
  fin >> N >> M;
  triple mn = {{INF, -1, -1}};
  rep(i, M) {
    fin >> a >> b >> c;
    --a, --b;
    G[a].push_back({c, b});
    G[b].push_back({c, a});
    if (mn > triple({{c, a, b}})) {
      mn = {{c, a, b}};
    }
  }

  vector<pii> res;
  int sum = mn[0];
  a = mn[1];
  b = mn[2];
  vis[a] = 1;
  vis[b] = 1;
  res.push_back({a,b});
  priority_queue<triple, vector<triple>, greater<triple> > q;
  for(int v: {a,b}) { // add all edges from a or b.
    for(pii X: G[v]) {
      if (!vis[X.second])
        q.push({{ X.first, v, X.second }});
    }
  }

  while(!q.empty()) {
    auto tr = q.top(); q.pop();
    int nod = tr[2];
    if (vis[nod])
      continue;
    vis[nod] = 1;
    sum += tr[0];
    res.push_back({tr[1],tr[2]});
    for(pii X: G[nod]) {
      if (!vis[X.second])
        q.push({{ X.first, nod, X.second}});
    }
  }

  fout << sum << '\n';
  fout << res.size() << endl;
  for(pii X: res) {
    fout << X.first + 1 << " " << X.second + 1 << '\n';
  }

  return 0;
}