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

using namespace std;

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

const int INF = INT_MAX;

vector<vector<pair<int, int>>> adj;
vector<pair<int, int>> edges;
int tata[200005];
int d[200005];

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

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

  input>>n>>m;

  vector<int> 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});
  }

  for (int i = 1; i <= n; i++) {
    d[i] = INF;
  }

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

  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;

    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] && c_x < d[u_x]){
        d[u_x] = c_x;
        tata[u_x] = u;
        pq.push({c_x, u_x});
      }
    }
  }

  output<<total<<endl;
  output<<edges.size()<<endl;

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

  return 0;
}