#include <cstdlib>
#include <fstream>
#include <cassert>

using namespace std;

const int MAX_N = 10000;
const int MAX_M = 1000000;

int n,m,v,u,w;
int G[MAX_N][MAX_N];

int tree[MAX_N][2];

int main() {
  int i;
  int sum = 0;
  ifstream fin("input.txt"); assert(fin);
  fin >> n >> m;    // n numero di nodi e m numero archi
  
  for(i = 0; i < m; i++){
    fin >> v >> u >> w;   
    G[v-1][u-1] = w;
    G[u-1][v-1] = w;
  }
  fin.close();

  for(i = 0; i < n; i++){
  
    for(int j = 0; j < n; j++){
      
      if(tree[j][0] == 0){
        tree[j][0] = G[i][j];
        tree[j][1] = i;
      } 
      else if(G[i][j] < tree[j][0] && G[i][j] != 0 && i < j) {   
        tree[j][0] = G[i][j]; // tree posizione n avra al suo interno peso, nodo comune.
        tree[j][1] = i;
      }

    }//for j
  
  }//for i

  for(i = 1; i < n; i++){
   sum += tree[i][0];
  }
  ofstream fout("output.txt"); assert(fout);
  fout << sum << endl;

  for(i = 1; i < n; i++){
    fout << tree[i][1]+1 << " " << i+1 << endl;  
  }

  fout.close();
  return 0;  

}