/* FILE: mst.cpp   last change: 30-Sep-2013   author: Alex Malfatti
 * a solver for problem mst
 */

#define NDEBUG   // NDEBUG definita nella versione che consegno
#include <cassert>
#ifndef NDEBUG
#  include <iostream>  // uso di cin e cout non consentito in versione finale
#endif
#include <fstream>
#include <climits>

using namespace std;

const int MAX_N = 10000;
const int MAX_M = 1000000;
int m, n;
int graph[MAX_N][MAX_N];
int parent[MAX_N];
int total_weight = 0;

int minKey(int key[], bool isNodeInMST[]) {
  int min = INT_MAX, min_index = 0;
 
  for (int i = 0; i < n; i++)
    if (isNodeInMST[i] == false && key[i] < min) {
      min = key[i];
      min_index = i;
    } 
  
  return min_index;
}

void mst() {
  int key[MAX_N];
  bool isNodeInMST[MAX_N];
 
  for (int i = 0; i < n; i++) {
    key[i] = INT_MAX;
    isNodeInMST[i] = false;
  }
 
  key[0] = 0;
  parent[0] = -1;
 
  for (int i = 0; i < n-1; i++) {
    int u = minKey(key, isNodeInMST);
 
    isNodeInMST[u] = true;
 
    for (int v = 0; v < n; v++)
      if (graph[u][v] && isNodeInMST[v] == false && graph[u][v] <  key[v])
        parent[v] = u, key[v] = graph[u][v];
     }

    for(int i = 0; i < n; i++)
      total_weight += key[i];

}

int main() {
  ifstream fin("input.txt"); assert( fin );
  fin >> n;
  fin >> m;  
  
  for(int i = 0; i < n; i++) {
    for(int j = 0; j < n; j++) {    
      graph[i][j] = 0;
    }  
  }

  for(int i = 0; i < m; i++) {
    int u, v;
    fin >> u;
    fin >> v;
    fin >> graph[u-1][v-1];
    graph[v-1][u-1] = graph[u-1][v-1];    
  }
  fin.close();

  mst(); 

  ofstream fout("output.txt"); assert( fout );
  fout << total_weight << endl;  
  for(int i = 1; i < n; i++)
      fout << parent[i]+1 << " " << i+1 << endl;
  fout.close();

  return 0;
}