#include <iostream>
#include <fstream>

using namespace std;

ifstream f("apm.in");
ofstream g("apm.out");

typedef struct { bool a,c; int b; } matrice;
matrice mat[100][100]={0};
int st[100],n,id[100],x=2,s=0;

bool verif(int a){
    for(int i=1;i<=x;i++)
        if(id[i]==a)
            return 0;
    return 1;
}

void scurt(){
    int cost=10000,l,a,b;
    for(int j=1;j<=x;j++){
    l=id[j];
    for(int i=l+1;i<=n;i++){
        if(mat[l][i].a==1 && mat[l][i].b<cost && mat[l][i].c==0 && verif(i)){
            cost=mat[l][i].b;
            a=l;
            b=i;
        }
    }
    }
    id[x++]=b;
    mat[a][b].c=1;
    mat[b][a].c=1;
    st[b]=a;
    s+=cost;
}

int main(){
    int i,j,a,b,c,m;
    f>>n>>m;
    for(i=1;i<=m;i++){
        f>>a>>b>>c;
        mat[a][b].a=1;
        mat[b][a].a=1;
        mat[a][b].b=c;
        mat[b][a].b=c;
    }
    st[1]=0;
    id[1]=1;
    for(i=1;i<n;i++){
        scurt();
    }
    g<<s<<endl<<n-1<<endl;
    for(i=1;i<=n;i++){
        for(j=i+1;j<=n;j++){
            if(mat[i][j].c==1){
                g<<i<<" "<<j<<endl;
            }
        }
    }

    return 0;
}