#include<fstream>
#include<algorithm>
#define dim 200007
using namespace std;

ifstream f("apm.in");
ofstream g("apm.out");
int T[2*dim],n,m,i,j,A[2*dim],b,sum,a;
struct cub{
    int x,y,c;
}
v[2*dim];
bool cmp(cub a ,cub  b) {
    return a.c<b.c;
}
int tata(int x) {
   if(T[x]<0)
        return x;
    T[x]=tata(T[x]);
    return T[x];
}
int main () {

    f>>n>>m;

    for(i=1;i<=m;++i){
        f>>v[i].x>>v[i].y>>v[i].c;
    }
    sort(v+1,v+1+m,cmp);
    for(i=1;i<=n;++i)
        T[i]=-1;
    int nr=0;
    for(i=1;i<=m;++i){
        a=tata(v[i].x);
        b=tata(v[i].y);

        if(a!=b){

            T[a]=T[a]+T[b];
            T[b]=a;
            sum+=v[i].c;
            ++nr;
            A[nr]=i;
        }

    }
    g<<sum<<"\n";
    g<<nr<<"\n";
    for(i=1;i<=nr;++i){
        b=A[i];
        g<<v[i].x<<" "<<v[i].y<<"\n";

    }
    return 0;
}