#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 x1[MAXN], y1[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 x,int y){

    while(tata[x] != 0)
        x = tata[x];
    while(tata[y] != 0)
        y = tata[y];

    if(h[x] < h[y]){
        tata[x] = y;
        h[y] = h[y] + 1;
    }
    else{
        tata[y] = x;
        h[x] = h[x] + 1;
    }
}

int check(int x,int y){

    while(tata[x] != 0)
        x = tata[x];
    while(tata[y] != 0)
        y = tata[y];

    if(x == y)
        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]]);
                x1[j] = x[poz[i]];
                y1[j] = y[poz[i]];
                sum = sum + pond[poz[i]];
                ++j;
            }
            ++i;
        }

    g << sum << "\n";

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

int main(){

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

}