#include<stdio.h>
#include<algorithm>
using namespace std;
struct muchie{int x,y,c,pp;};
muchie v[400005];
int tata[200005];
bool comp(muchie a,muchie b){
    if(a.c<=b.c)
        return true;
    return false;
}

int dad(int x){
    if(x==tata[x])
        return x;
    else
        return tata[x]=dad(tata[x]);
}
void minion(int x, int y){
    int tx,ty;
    tx=dad(x);
    ty=dad(y);
    tata[tx]=ty;
}

int main(){
    freopen("apm.in","r",stdin);
    freopen("apm.out","w",stdout);
    int n,m,i,s,cate=0;
    scanf("%d%d",&n,&m);
    for(i=1;i<=m;i++){
        scanf("%d%d%d",&v[i].x,&v[i].y,&v[i].c);
    }
    for(i=1;i<=n;i++)
        tata[i]=i;
    sort(v+1,v+m+1,comp);
    s=0;
    for(i=1;cate<n-1;i++){
        if(dad(v[i].x)!=dad(v[i].y)){
            cate++;
            minion(v[i].x,v[i].y);
            v[i].pp=1;
            s+=v[i].c;
        }
    }
    printf("%d\n%d\n",s,n-1);
    for(i=1;i<=m;i++)
        if(v[i].pp==1)
            printf("%d %d\n",v[i].x,v[i].y);
    return 0;
}