#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>

#define max 400100
using namespace std;

ifstream in("apm.in");
ofstream out("apm.out");

int n, m, x[max], y[max], cost[max], indice[max], gr[max], rez;
vector <int> apm;

inline bool cmp ( int a, int b ){

    return (cost[a] < cost[b]) ;
}

int padure(int i){

    if(gr[i] == i) return i;
    gr[i] = padure(gr[i]);
    return gr[i];
}

void reuneste (int i, int j){

    gr[padure(i)] = padure(j);
}

int main(){

    in >> n >> m;

    for( int i = 1 ; i <= m ; ++ i ){

        in>> x[i] >> y[i] >> cost[i];
        indice[i] = i ;
    }

    sort( indice + 1, indice + m + 1, cmp );

    for(int  j = 1;  j <= n ; ++ j)
        gr[j] = j ;

    for ( int i = 1 ; i <= m ; ++ i ){

        if(padure(x[indice[i]]) != padure(y[indice[i]])){

            rez += cost[indice[i]];
            reuneste ( x[indice[i]], y[indice[i]] ) ;
            apm.push_back(indice[i]);

        }
    }

    out<<rez<<"\n"<<n-1<<"\n";

    for( int i = 0 ; i < n-1 ; ++ i)
        out<<x[apm[i]]<<" "<<y[apm[i]]<<"\n";

    return 0;
}