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

using namespace std;

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

const int MAXN = 200000;

vector<pair<int, int>> g[MAXN + 1];

struct Edge {
  int u, v, w;
};

bool operator < (Edge a, Edge b) {
  return a.w > b.w;
}

priority_queue<Edge> pq;
int viz[MAXN + 1];
vector<Edge> edges;

int main() {
  int n, m;
  fin >> n >> m;
  for(int i = 1; i <= m; i++) {
    int u, v, w;
    fin >> u >> v >> w;
    g[u].push_back({v, w});
    g[v].push_back({u, w});
  }

  int answer = 0;
  pq.push({1, 1, 0});
  while(!pq.empty()) {
    Edge curr = pq.top();
    pq.pop();
    int node = curr.v;
    if(!viz[node]) {
      viz[node] = 1;
      answer += curr.w;
      edges.push_back(curr);
      for(auto edge : g[node]) {
        if(!viz[edge.first]) {
          pq.push({node, edge.first, edge.second});
        }
      }
    }
  }

  fout << answer << "\n" << n - 1 << "\n";
  for(int i = 1; i < n; i++) {
    fout << edges[i].u << " " << edges[i].v << "\n";
  }

  return 0;
}