#include <fstream>
#include <vector>
#include <queue>
using namespace std;

#define NMAX 200001
#define INF 0x3f3f3f3f

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

int n, m, P[NMAX], sum;
vector<pair<int, int>> G[NMAX];

void prim(int source) {
  priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> PQ;
  vector<int> D(n + 1, INF);
  vector<bool> InAPM(n + 1, false);
  
  PQ.push({0, source});
  D[source] = 0;
  
  while (!PQ.empty()) {
    int node = PQ.top().second;
    int test = PQ.top().first;
    PQ.pop();
    
    if (InAPM[node] == true)
      continue;
      
    sum += test;
    InAPM[node] = true;
      
    for (auto next : G[node]) {
      int neigh = next.first;
      int weight = next.second;
      
      if (InAPM[neigh] == false && weight < D[neigh]) {
        D[neigh] = weight;
        PQ.push({D[neigh], neigh});
        P[neigh] = node;
      }
    }
  }
}

int main() {
  cin >> n >> m;
  for (int i = 1, u, v, c; i <= m; ++i) {
    cin >> u >> v >> c;
    G[u].push_back({v, c});
    G[v].push_back({u, c});
  }
  
  prim(1);
  
  cout << sum << "\n" << n - 1 << "\n";
  for (int i = 2; i <= n; ++i)
    cout << i << " " << P[i] << "\n";
  
  cin.close();
  cout.close();
  return 0;
}