#include <fstream>
#include <vector>
#include <queue>

using namespace std;

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

const int MAXN = 2e5;
const int MAXM = 4e5;
const int MAXC = 1e3;

struct muchie {
  int a;
  int b;
  int c;

  muchie(int _a = 0, int _b = 0, int _c = 0) {
    a = _a; b = _b; c = _c;
  }
}mu;

class cmp{
  public :
    bool operator() (const muchie a, const muchie b) const {
      return a.c > b.c;
    }
};

vector <pair <int, int>>g[MAXN + 1];
priority_queue <muchie, vector <muchie>, cmp>pq;
int n, m;
queue <muchie>ans;
bool viz[MAXN + 1];
int s, cnt;

void apm(int nod) {
  viz[nod] = 1;
  for (auto x : g[nod]) {
    if (!viz[x.first]) {
      mu.a = nod;
      mu.b = x.first;
      mu.c = x.second;
      pq.push(mu);
    }
  }

  while (pq.size() && viz[pq.top().b]) {
    pq.pop();
  }

  if (pq.size()) {
    ans.push(pq.top());
    ++ cnt;
    s += pq.top().c;
    int urm = pq.top().b;
    pq.pop();
    apm(urm);
  }
}

int main() {
  in >> n >> m;

  for (int i = 1; i <= m; ++ i) {
    in >> mu.a >> mu.b >> mu.c;
    g[mu.a].push_back({mu.b, mu.c});
    g[mu.b].push_back({mu.a, mu.c});
  }

  apm(1);

  out << s << '\n' << cnt << '\n';

  while (ans.size()) {
    out << ans.front().a << ' ' << ans.front().b << '\n';
    ans.pop();
  }

  return 0;
}