#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <algorithm>
#define M 400100
#define N 200100


using namespace std;

struct muchie{
    int x,y,c;
};
struct muchie muc[M];

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

muchie stk[N];
int sp;
void push(muchie t){
    stk[sp++]=t;
}

int tata[N];
int findtat(int x){
    static int t,t2;
    t=x;
    while(tata[x]>=0){
        x=tata[x];
    }
    while(tata[t]>=0){
        t2=tata[t];
        tata[t]=x;
        t=t2;
    }
    return x;
}
void merget(int x,int y){
    static int t;

    if(-tata[x]<-tata[y]){
        t=x;
        x=y;
        y=t;
    }
    tata[x]+=tata[y];
    tata[y]=x;
}


int main(){
    int n,m;
    int i,x,y,j;
    int cost,costtot=0;
    int spy,t1,t2;

    freopen("apm.in","r",stdin);
    freopen("apm.out","w",stdout);

    scanf("%d%d",&n,&m);
    memset(tata,-1,(n+1)*sizeof(int) );
    for(i=0;i<m;i++){
        scanf("%d%d%d",&x,&y,&cost);
        muc[i].x=x;
        muc[i].y=y;
        muc[i].c=cost;
    }
    sort(muc,muc+m,cmp);

    for(i=0,j=0;i<n-1;i++){
        spy=1;
        while(spy){
            x=muc[j].x;
            y=muc[j].y;

            t1=findtat(x);
            t2=findtat(y);
            if(t1!=t2){
                spy=0;
                merget(t1,t2);
                push(muc[j]);
                costtot+=muc[j].c;
            }
            j++;
        }
    }
    printf("%d\n",costtot);
    printf("%d\n",sp);
    for(i=0;i<sp;i++){
        printf("%d %d\n",stk[i].x,stk[i].y);
    }
    return 0;
}