#include <cassert>
#  include <iostream> 
#include <fstream>
#include <string>

using namespace std;

const int MAX_N = 10000;
const int MAX_M = 1000000;
int m, n, somma;
int input[MAX_M][3];
int output[MAX_M][2];
int liste[MAX_N][MAX_N];//creo liste per insiemi disgiunti
int lunghezzal[MAX_N];


int main() {
ifstream fin("input.txt"); assert( fin );
fin >> n >> m;

for(int i = 0; i < m; i++) {
    fin>>input[i][1];
    fin>>input[i][2];
    fin>>input[i][3];
}

int appoggio[3];

//ordino gli archi per peso
for(int i=0; i<(m-1); i++){
   for(int j=i+1; j<m; j++){
      if(input[i][3]>input[j][3]){
        appoggio[1]=input[j][1];
        appoggio[2]=input[j][2];
        appoggio[3]=input[j][3];
        input[j][1]=input[i][1];
        input[j][2]=input[i][2];
        input[j][3]=input[i][3];
        input[i][1]=appoggio[1];
        input[i][2]=appoggio[2];
        input[i][3]=appoggio[3];
       }
   }
}

for(int j=0; j<MAX_N; j++){
    for(int l=0; l<MAX_N; l++){
        liste[j][l]=0;
}}

//utilizzo kruskal
int nliste=1;
int primon, secondon;
bool primo, secondo;
primon=0;
secondon=0;
somma=0;

//inserisco il primo elemento
output[0][1]=input[0][1];
output[0][2]=input[0][2];
somma=somma+input[0][3];

liste[0][0]=1;
liste[0][1]=input[1][1];
liste[0][2]=input[1][2];
lunghezzal[0]=2;

int counto=1;
for(int i = 1; i < m; i++) {
    int j=0;
    primo=false;
    secondo=false;
    while (j<nliste){
        int l=0;
        while(liste[j][l]!=0){
            if(input[i][1]==liste[j][l]){
                if(primo!=true){
                    primon=j;
                    primo=true;
                }
            }
            if(input[i][2]==liste[j][l]){
                if(secondo!=true){
                    secondon=j;
                    secondo=true;
                }
            }
            l++;
        }
        lunghezzal[j]==l;
        j++;
    }
//casi

        if(primo==true && secondo==true && primon==secondon){ //stessa lista....non aggiungo
        }
        else{
            output[counto][1]=input[i][1];
            output[counto][2]=input[i][2];
            somma=somma+input[i][3];
            counto++;

            if(primo==true){//primo in lista
                if(secondo==true){//entrambi in liste diverse
                    int z=1;
                    liste[secondon][0]=0;
                    int l=lunghezzal[primon];
                    while(liste[secondon][z]!=0){
                        liste[primon][l]=liste[secondon][z];
                        liste[secondon][z]=0;
                        z++;
                        l++;
                    }
                    lunghezzal[primon]=l;
                }else//primo ma non secondo
                   {liste[primon][lunghezzal[primon]]==input[i][2];}
            
            }
            else if(secondo==true){//solo il secondo già in lista
                liste[secondon][lunghezzal[secondon]]==input[i][1];
            }
            if(primo==false && secondo==false){
                nliste++;
                liste[nliste][0]=1;
                liste[nliste][1]=input[i][1];
                liste[nliste][2]=input[i][2];
            }
        }

}

    
//scrivo output
ofstream fout("output.txt"); assert( fout );
fout<<somma<<endl;
for(int i = 0; i < m; i++) {
    fout<<output[i][1]<<" ";
    fout<<output[i][2]<<" ";
    fout<<endl;
}

fout.close();

return 0;
}