#include <fstream>
#include <algorithm>
using namespace std;
ifstream in("apm.in");
ofstream out("apm.out");

struct Muchie {int x,y,c;}G[(100 * 99)/2];
int N,M,mini,maxi,Nr,Cost;
int c[(100*99)/2],A[(100*99)/2];


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;
}