#include <fstream>
#include <vector>
#include <queue>
#include <cstring>
#include <stack>

using namespace std;

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

vector<vector<pair<int, int>>> adj;
vector<pair<int, int>> edges;
vector<pair<int, int>> tata;

int main() {
  priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
  int total = 0;
  int noduri = 0;

  int n, m, k;
  int x, y, w;

  input>>n>>m;

  vector<int> tata(n + 1, 0), viz(n + 1, 0);
  adj.resize(n + 1);

  for(int i = 0; i < m; i++){
    input>>x>>y>>w;

    adj[x].push_back({w, y});
    adj[y].push_back({w, x});
  }

  pq.push({0, 1});
  tata[1] = 0;

  while(!pq.empty()){
    int c = pq.top().first;
    int u = pq.top().second;
    pq.pop();

    if(viz[u] == 1) continue;

    viz[u] = 1;
    total += c;
    noduri++;

    if(u != 1){
      edges.push_back({u, tata[u]});
    }

    for(pair<int, int> x : adj[u]){
      int c_x = x.first;
      int u_x = x.second;

      if(!viz[u_x]){
        tata[u_x] = u;
        pq.push({c_x, u_x});
      }
    }
  }

  output<<total<<endl;
  output<<noduri - 1<<endl;

  for(auto& edge : edges){
    output<<edge.first<<" "<<edge.second<<endl;
  }



  return 0;
}