#include <cstdlib>
#include <fstream>
#include <cassert>
#include <iostream>
using namespace std;


const int N = 10000;
const int M = 1000000;
int Grafo [1000000][3];

void quickSort(int left, int right) {
      int i = left, j = right;
      int tmp0, tmp1, tmp2;
      int pivot = Grafo[(left + right) / 2][2];
 
      /* partition */
      while (i <= j) {
            while (Grafo[i][2] < pivot)
                  i++;
            while (Grafo[j][2] > pivot)
                  j--;
            if (i <= j) {
                  tmp0 = Grafo[i][0];
                  tmp1 = Grafo[i][1];
                  tmp2 = Grafo[i][2];
                  Grafo[i][0] = Grafo[j][0];
                  Grafo[i][1] = Grafo[j][1];
                  Grafo[i][2] = Grafo[j][2];
                  Grafo[j][0] = tmp0;
                  Grafo[j][1] = tmp1;
                  Grafo[j][2] = tmp2;
                  i++;
                  j--;
            };
      }

      /* recursion */
      if (left < j)
            quickSort(left, j);
      if (i < right)
            quickSort(i, right);

}




int main () {


int Risultato [1000000][2];
int somma=0;
int Coverage [10000];
ifstream input("input.txt"); assert(input);
//leggi valori attuali N e M
ofstream output("output.txt"); assert(output);
int actN;
input >> actN;
int actM;
input >> actM;
int nodo1, nodo2, arco;
nodo1=0;
nodo2=0;
arco=0;
while (arco<actN) {
    Coverage[arco]=0;
    arco++;
}
arco=0;
//inizializza Grafo;
while (arco<actM) {
    input >> Grafo[arco][0];
    input >> Grafo[arco][1];
    input >> Grafo[arco][2];
    arco++;
}

quickSort(0,actM-1);
arco =0;
while (arco<actM) {
    arco++;
}
arco=1;
int counter=1;
Coverage[Grafo[0][0]]++;
Coverage[Grafo[0][1]]++;
somma=somma+Grafo[0][2];
Risultato[0][0]=Grafo[0][0];
Risultato[0][1]=Grafo[0][1];

while (counter<actM-2){
while (arco<=8) {

    if (
          ( ((Coverage[Grafo[arco][0]] * Coverage[Grafo[arco][1]])==0) )  &&
          ( ((Coverage[Grafo[arco][0]] + Coverage[Grafo[arco][1]])>0) )
       ) {
        Coverage[Grafo[arco][0]]++;
        Coverage[Grafo[arco][1]]++;
        Risultato[counter][0]=Grafo[arco][0];
        Risultato[counter][1]=Grafo[arco][1];
        somma=somma+Grafo[arco][2];

        counter++;

arco=8;
    }
    arco++; 
}
arco=0;
}

//scrivi output

    output << somma; output << "\n";

arco=0;
while (arco<counter){
    output << Risultato[arco][0];
    output << " ";
    output << Risultato[arco][1];  
    output << "\n";
    arco++;
}
}