#include<cstdio>
#include<vector>
#include<algorithm>
using namespace std;
#define pp pair < int,int >
#define ff first
#define ss second
#define MAX 200002
#define inf 200000200
vector < pp > v[MAX],sol;
int val[MAX],H[2*MAX+10],poz[MAX],M[MAX];
int n,m,hp,cost;
void add_to_APM(int nod){
    unsigned i;
    for(i=0;i<v[nod].size();++i){
        pp aux=v[nod][i];
        val[aux.ff]=min(val[aux.ff],aux.ss);
        if(val[aux.ff]==aux.ss)
            M[aux.ff]=nod;
    }
}
void swift(int p){
    int son;
    do{
        son=0;
        if(p*2<=hp){
            son=p*2;
            if((p*2)+1<=hp && val[H[(p*2)+1]]<val[H[son]])
                son=(p*2)+1;
            if(val[H[p]]<=val[H[son]])
                son=0;
        }
        if(son){
            swap(H[p],H[son]);
            swap(poz[H[p]],poz[H[son]]);
            p=son;
        }
    }while(son);
}
void percolate(int p){
    while(p>1 && val[H[p]]<val[H[p/2]]){
        swap(H[p],H[p/2]);
        swap(poz[H[p]],poz[H[p/2]]);
        p=p/2;
    }
}
void add_to_heap(int k){
    H[++hp]=k;
    poz[k]=hp;
    percolate(poz[k]);
}
int extract_min(){
    int root=H[1];
    swap(H[1],H[hp]);
    swap(poz[H[1]],poz[H[hp]]);
    hp--;
    swift(1);
    poz[root]=0;
    return root;
}
int main(){
    int i,a,b,c;
    freopen("apm.in","r",stdin);
    scanf("%d%d",&n,&m);
    for(i=1;i<=m;i++){
        scanf("%d%d%d",&a,&b,&c);
        v[a].push_back(make_pair(b,c));
        v[b].push_back(make_pair(a,c));
    }
    fclose(stdin);
    for(i=1;i<=n;i++)
        val[i]=inf;
    val[1]=0;
    add_to_APM(1);
    for(i=2;i<=n;i++)
        add_to_heap(i);
    for(i=1;i<n;i++){
        int MIN=extract_min();
        add_to_APM(MIN);cost+=val[MIN];
        sol.push_back(make_pair(MIN,M[MIN]));
        for(int j=0;j<(int)v[MIN].size();j++)
            if(poz[v[MIN][j].ff])
                percolate(poz[v[MIN][j].ff]);
    }
    freopen("apm.out","w",stdout);
    printf("%d\n%d",cost,n-1);
    for(i=0;i<n-1;++i)
        printf("\n%d %d",sol[i].ff,sol[i].ss);
    fclose(stdout);
    return 0;
}