#include <fstream>
#include <algorithm>
#include <vector>
#include <cmath>

using namespace std ;

const int NMAX = 400005 ;
const int INF = 0x3f3f3f3f ;

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

int graf[NMAX], X[NMAX], Y[NMAX], C[NMAX] ;
int N, M, sol, rez[NMAX] ;
vector <int> V ;

int grupa(int i)
{

    if(graf[i] == i)
        return i ;
    graf[i] = grupa(graf[i]) ;
    return graf[i] ;
}


void RNM(int x, int y)
{

    graf[grupa(x)] = grupa(y) ;
}

bool Verif(int x, int y)
{

    return (C[x] < C[y]) ;
}


int main()
{
    fin >> N >> M;

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

        fin >> X[i] >> Y[i] >> C[i] ;
        rez[i] = i ;

    }

    for(int i = 1 ; i <= N ; ++ i)
        graf[i] = i ;

    sort(rez + 1, rez + M + 1, Verif) ;

    for(int i = 1 ; i <= M ; ++ i)
        if(X[rez[i]] != grupa(Y[rez[i]]))
        {
            sol = sol + C[rez[i]] ;
            RNM(X[rez[i]], Y[rez[i]]) ;
            V.push_back(rez[i]) ;
        }


    fout << sol << '\n';
    fout << N - 1 << '\n' ;

    for(int i = 0 ; i < N - 1 ; ++ i)
        fout << X[V[i]] << ' ' << Y[V[i]] << '\n' ;

    fin.close() ;
    fout.close() ;
    return 0 ;
}