//Algoritmul lui Prim
#include <stdio.h>
#define INF 1001
#define MAXN 200000
#define MAXM 400000
char selected[MAXN+1];
int cost[MAXM*2+1], val[MAXM*2+1], next[MAXM*2+1];
int lista[MAXN+1], d[MAXN+1], t[MAXN+1], heap[MAXN+1], poz[MAXN+1], rasp1[MAXN+1], rasp2[MAXN+1];
int n;
inline void coborare(int x){
    int q, f, aux, fiu1, fiu2;
    f=1;
    while(f==1){
        fiu1=x*2;
        fiu2=x*2+1;
        q=-1;
        if(fiu2<=n){
            q=fiu2;
        }
        if(((q==-1)&&(fiu1<=n))||((q!=-1)&&(d[heap[fiu2]]>d[heap[fiu1]]))){
            q=fiu1;
        }
        if((q!=-1)&&(d[heap[q]]<d[heap[x]])){
            poz[heap[q]]=x;
            poz[heap[x]]=q;
            aux=heap[q];
            heap[q]=heap[x];
            heap[x]=aux;
            x=q;
        }else{
            f=0;
        }
    }
}
inline void urcare(int x){
    int f, aux;
    f=1;
    while((f==1)&&(x>1)){
        if(d[heap[x/2]]>d[heap[x]]){
            poz[heap[x/2]]=x;
            poz[heap[x]]=x/2;
            aux=heap[x/2];
            heap[x/2]=heap[x];
            heap[x]=aux;
            x/=2;
        }else{
            f=0;
        }
    }
}
inline int costul(int a, int b){
    int p, x;
    x=INF;
    for(p=lista[a]; p!=0; p=next[p]){
        if(b==val[p]){
            x=cost[p];
        }
    }
    return x;
}
int main(){
    int m, i, x, y, z, nr, nod, p;
    FILE *fin, *fout;
    fin=fopen("apm.in", "r");
    fout=fopen("apm.out", "w");
    fscanf(fin, "%d%d", &n, &m);
    for(i=1; i<=m; i++){
        fscanf(fin, "%d%d%d", &x, &y, &z);
        cost[i*2-1]=z;
        val[i*2-1]=y;
        next[i*2-1]=lista[x];
        lista[x]=i*2-1;
        cost[i*2]=z;
        val[i*2]=x;
        next[i*2]=lista[y];
        lista[y]=i*2;
    }
    for(i=1; i<=n; i++){
        d[i]=INF;
        heap[i]=i;
        poz[i]=i;
    }
    nr=0;
    nod=1;
    selected[1]=1;
    for(i=1; i<n; i++){
        for(p=lista[nod]; p!=0; p=next[p]){
            if((selected[val[p]]==0)&&(d[val[p]]>cost[p])){
                d[val[p]]=cost[p];
                t[val[p]]=nod;
                urcare(poz[val[p]]);
            }
        }
        nr+=d[heap[1]];
        selected[heap[1]]=1;
        rasp1[i]=t[heap[1]];
        rasp2[i]=heap[1];
        d[heap[1]]=INF;
        nod=heap[1];
        coborare(1);
    }
    fprintf(fout, "%d\n%d\n", nr, n-1);
    for(i=1; i<n; i++){
        fprintf(fout, "%d %d\n", rasp1[i], rasp2[i]);
    }
    fclose(fin);
    fclose(fout);
    return 0;
}