#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 = 1000;

int n, m;
vector <pair <int, int>>g[MAXN + 1];
bool viz[MAXN + 1];

class cmp {
  public :
    bool operator() (const pair <int, int>a, const pair <int, int>b) const {
      return a.second > b.second;
    }
};

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

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

  priority_queue <pair <int, int>, vector <pair <int, int>>, cmp>pq;
  queue <int>nodes;

  viz[1] = true;
  nodes.push(1);
  int cnt = 0, s = 0;
  queue <pair <int, int>>ans;

  while (nodes.size()) {
    for (auto x : g[nodes.front()]) {
      if (!viz[x.first])
        pq.push(x);
    }

    while (pq.size() && viz[pq.top().first])
      pq.pop();

    if (pq.size()) {
      nodes.push(pq.top().first);
      viz[pq.top().first] = 1;
      s += pq.top().second;
      ++ cnt;
      ans.push({nodes.front(), pq.top().first});
      pq.pop();
    }
    nodes.pop();

  }

  out << s << '\n' << cnt << '\n';
  while (ans.size()) {
    out << ans.front().first << ' ' << ans.front().second << '\n';
    ans.pop();
  }
  return 0;
}