#include <iostream>
#include <fstream>
#include <algorithm>
#define MAXN 400100

using namespace std;

int n, m, x[MAXN], y[MAXN], pond[MAXN], poz[MAXN], tata[MAXN], h[MAXN];
int x_final[MAXN], y_final[MAXN];

void read(){

    fstream f("apm.in",ios::in);

    f >> n >> m;

    int i = 1;

    while(f >> x[i] >> y[i] >> pond[i]){
        poz[i] = i;
        ++i;
    }

    for(i = 1;i <= n; ++i)
        tata[i] = h[i] = 0;
}

int cmp(int i,int j){

    return (pond[i] < pond[j]);
}

void add(int a,int b){

    while(tata[a] != 0)
        a = tata[a];
    while(tata[b] != 0)
        b = tata[b];

    if(h[a] < h[b]){
        tata[a] = b;
        h[b] = h[b] + 1;
    }
    else{
        tata[b] = a;
        h[a] = h[a] + 1;
    }
}

int check(int a,int b){

    while(tata[a] != 0)
        a = tata[a];
    while(tata[b] != 0)
        b = tata[b];

    if(a == b)
        return 1;
    return 0;
}

void solve(){

    int sum = 0, i = 1, j = 1;

    fstream g("apm.out",ios::out);

        while(j < n){
            if(!check(x[poz[i]],y[poz[i]])){
                add(x[poz[i]],y[poz[i]]);
                x_final[j] = x[poz[i]];
                y_final[j] = y[poz[i]];
                sum = sum + pond[poz[i]];
                ++j;
            }
            ++i;
        }

    g << sum << "\n";

    for(i = 1;i < n; ++i)
        g << x_final[i] << " " << y_final[i] << "\n";
}

int main(){

    read();
    sort(poz + 1,poz + m + 1,cmp);
    solve();
    return 0;

}