#include <fstream>

#include <algorithm>

using namespace std;

ifstream in("apm.in");

ofstream out("apm.out");



struct Muchie {int x,y,c;}G[200010];

int N,M,mini,maxi,Nr,Cost;

int c[400010],A[400010];





bool cmp(Muchie A, Muchie B){

    return A.c < B.c;

}

int main(){

    in >> N >> M;

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

        in >> G[i].x >> G[i].y >> G[i].c;



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

        c[i] = i;



    sort(G+1,G+M+1,cmp);



    Nr = 0;

    for(int i = 1; Nr < N-1; ++i){

        if(c[G[i].x] != c[G[i].y])

            A[++Nr] = i;



        if(c[G[i].x] < c[G[i].y]) mini = c[G[i].x], maxi = c[G[i].y];

            else

                mini = c[G[i].y], maxi = c[G[i].x];



    for(int j = 1; j <= N; ++j)

        if(c[j] == maxi)

            c[j] = mini;

    }





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

        Cost+= G[A[i]].c;

    }



    out << Cost << '\n';

    out << N-1 << '\n';

    for(int i = 1; i < N; ++i)

        out << G[A[i]].x << " " << G[A[i]].y << '\n';





    return 0;

}