#include <stdio.h>
#include <stdlib.h>
#include <algorithm>

#define BUF_SIZE 16384
char buf[BUF_SIZE];
int pbuf=BUF_SIZE;
FILE*fi,*fo;
inline char nextch(){
    if(pbuf==BUF_SIZE){
        fread(buf, BUF_SIZE, 1, fi);
        pbuf=0;
    }
    return buf[pbuf++];
}
inline long long nextnum(){
    long long a=0;
    char c=nextch();
    while((c<'0' || c>'9') && c!='-')
        c=nextch();
    int semn=1;
    if(c=='-'){
        semn=-1;
        c=nextch();
    }
    while('0'<=c && c<='9'){
        a=a*10+c-'0';
        c=nextch();
    }
    return a*semn;
}

#define MAXM 400000
#define MAXN 200000

struct muchie{
    int left;
    int right;
    int cost;
} M[1+MAXM];

int fth[1+MAXN];
int st[1+MAXN], ind=0;

inline int Union(int a, int b){
    fth[b]=a;
}
int Find(int x){
    if(fth[x]==x)
        return x;
    int y=Find(fth[x]);
    fth[x]=y;
    return y;
}

int cmpM(muchie A, muchie B){
    return (A.cost<B.cost);
}

int main(){
    fi=fopen("apm.in","r");
    fo=fopen("apm.out","w");
    int n=nextnum(), m=nextnum();
    for(int i=1;i<=m;i++){
        M[i].left=nextnum();
        M[i].right=nextnum();
        M[i].cost=nextnum();
    }
    std::sort(M+1, M+m+1, cmpM);
    for(int i=1;i<=n;i++)
        fth[i]=i;
    int cost=0;
    for(int i=1;i<=m;i++){
        //printf("%d %d %d ", M[i].left, M[i].right, M[i].cost);
        if(Find(M[i].left)!=Find(M[i].right)){
            //printf("da");
            Union(Find(M[i].left), Find(M[i].right));
            cost+=M[i].cost;
            st[++ind]=i;
        }
    //printf("\n");
    }
    fprintf(fo,"%d\n%d\n", cost, n-1);
    for(int i=1;i<=ind;i++)
        fprintf(fo,"%d %d\n", M[st[i]].left, M[st[i]].right);
    fclose(fi);
    fclose(fo);
    return 0;
}