#include <algorithm>
#include <fstream>

#define NMax 400005
using namespace std;
ifstream f("apm.in");
ofstream g("apm.out");

struct muchie{
    int x,y,c;
}G[NMax];

int n,m,Rx,Ry,cost,muchii;
int r[NMax],sol[NMax],rang[NMax];

int cmp(muchie x,muchie y){
    return (x.c < y.c);
}
int root(int x){
    while(r[x])
        x = r[x];
    return x;
}
void kruskal(){
    for(int i = 1; i <= m; ++i){
        rang[i] = 1;
    }
    for(int i = 1; i <= m && muchii < n - 1; ++i){
        Rx = root(G[i].x);
        Ry = root(G[i].y);

        if(Rx != Ry){
            sol[++muchii] = i;
            cost += G[i].c;

            if(rang[Rx] > rang[Ry]){
                rang[Rx] += rang[Ry];
                r[Ry] = Rx;
            }else{
                rang[Ry] += rang[Rx];
                r[Rx] = Ry;
            }
        }
    }
}
int main()
{
    f >> n >> m;
    for(int i = 1; i <= m; ++i){
        f >> G[i].x >> G[i].y >> G[i].c;
    }
    sort(G + 1, G + 1 + m,cmp);
    kruskal();
    g << cost <<"\n" << n - 1 <<"\n";
    for(int i = 1; i < n; ++i){
        g << G[sol[i]].x <<" " << G[sol[i]].y <<"\n";
    }
    return 0;
}