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

struct minTree{
    int a;
    int b;
};

int m,n;
int x,y;
long w;
const int M_MAX=1000000;
const int N_MAX=10000;
int matrix[N_MAX][N_MAX];
minTree tree[N_MAX-1];
long sum_w;
void min_st(){
//ricerca del minimo per ogni colonna...
//la matrice è costruita come una triangolare superiore.
long min;
//cout<<min<<endl;


for(int i=1; i<n;i++){
   min=2000000;
    for(int j=0; j <i;j++){
       //cerco il minimo peso per ogni nodo scandendo le colonne. Di esso salvo gli indici nella matrice di adiacenza
        if(matrix[j][i] < min && matrix[j][i]>0){
            min=matrix[j][i];
            x=j+1; y=i+1;
            }
        //ho finito di scandire ogni riga della colonna, quindi il minimo corrente è il minimo da salvare nell'albero.
        if(j==i-1){
            tree[i-1].a=x; 
            tree[i-1].b=y;
            //cout<<tree[i-1].a<<" "<<tree[i-1].b<<" ";
            //x=j+1; y=i+1;
            sum_w +=matrix[x-1][y-1];
            //cout<<sum_w<<endl;
        }
      //    if(j==i-1)  
        //fout << x << " " << y << " \n";
    }
}
}
/*void stampa(){
    for(int i=0; i<n;i++)
        for(int j=0;j<n;j++)
            if(matrix[i][j] != 0)
            //cout<<i+1<<" "<<j+1<<" "<<matrix[i][j]<<endl;
}*/

int main(){
    ifstream fin("input.txt"); assert(fin);
    fin >> n >> m;
    for(int i=0;i<m;i++){
        fin >> x >> y >> w;
        if(x<y)
            matrix[x-1][y-1]=w;
        else
            matrix[y-1][x-1]=w;
    }
//stampa();
        
    min_st();
ofstream fout("output.txt"); assert(fout);
fout << sum_w<<endl;
for(int i=0; i<n-1;i++)
    fout << tree[i].a <<" " << tree[i].b <<endl;
}