#include<fstream>
#include<algorithm>

using namespace std;

ifstream f("apm.in");
ofstream g("apm.out");

struct muchie{

    int n1, n2, cost;
};

const int Nmax = 200005;
const int Mmax = 400005;

muchie m[Mmax], sol[Mmax];
int n, M, N, k = 1;
int father[Nmax], level[Nmax], cost_minim;

bool cmp(muchie a, muchie b){

    return a.cost < b.cost;
}

void read_data(){

    f >> n >> M;
    for(int i = 1; i <= M; i++)
        f >> m[i].n1 >> m[i].n2 >> m[i].cost;
    sort(m + 1, m + M + 1, cmp);
}

inline int find_root(int x){

    int i, y;

    for(i = x; father[i] != i; i = father[i]);

    while(father[i] != i){

        y = father[i];
        father[i] = i;
        x = y;
    }

    return i;
}

inline void unit(int x, int y){

    if(level[x] > level[y])
        father[y] = x;
    else
        father[x] = y;

    if(level[x] == level[y])
        level[y]++;
}

void Kruskal(){

    int i, a, b;
    for(i = 1; i <= n; i++){

        father[i] = i;
        level[i] = 1;
    }

    for(i = 1; i < n;){

        a = find_root(m[k].n1);
        b = find_root(m[k].n2);
        if(a != b){

            N++;
            sol[N].n1 = m[k].n1;
            sol[N].n2 = m[k].n2;
            cost_minim += m[k].cost;
            ++i;

            unit(a, b);
        }
        ++k;
    }

    g << cost_minim << '\n' << n - 1 << '\n';
    for(i = 1; i < n; i++)
        g << sol[i].n1 << ' ' << sol[i].n2 << '\n';
}

int main(){

    read_data();
    Kruskal();

}