#include <fstream>
#include <algorithm>
using namespace std;
 ifstream f("apm.in");
 ofstream g("apm.out");
int n,m,cost,nr,sol[200011];
int T[200011];

struct muchii{
    int x;
    int y;
    int c;
};
muchii v[400013];

inline int cmp(muchii a,muchii b){
    return (a.c<b.c);
}

int rad(int x){
    int y=x,aux;
    while(T[x]>0)
        x=T[x];
    while(T[y]>0){
        aux=T[y];
        T[y]=x;
        y=aux;
    }
    return x;
}

int main(void){
    register int i,j,x,y;

    f>>n>>m;
    for(i=1;i<=m;i++)
        f>>v[i].x>>v[i].y>>v[i].c;

    sort(v+1,v+m+1,cmp);

    for(i=1;i<=n;i++){
        T[i]=-1;
    }


    for(i=1;i<=m;i++){
        x=rad(v[i].x);
        y=rad(v[i].y);
        if(x!=y){
            if(T[x]<T[y]){
                T[x]+=T[y];
                T[y]=x;
            }
            else{
                T[y]+=T[x];
                T[x]=y;
            }
            sol[++sol[0]]=i;
            cost+=v[i].c;
        }
    }

    g<<cost<<"\n"<<sol[0]<<"\n";
    for(i=1;i<=sol[0];i++){
        g<<v[sol[i]].x<<" "<<v[sol[i]].y<<"\n";
    }
    return 0;
 }