#include <bits/stdc++.h>
#define minf -2000000000
std::priority_queue< std::pair<int,int> > h;

std::vector<int> nod[200000][2];

int best[200000][2];

char frq[200000];

void reset(){
    for(int i=0;i<200000;i++){
        best[i][0]=-1;
        best[i][1]=minf;
    }
}

int main()
{
    int n,m,i,a,b,c,s,nd,val,sum=0,nd2,val2;
    FILE*fi,*fo;
    fi=fopen("apm.in","r");
    fo=fopen("apm.out","w");
    fscanf(fi,"%d%d",&n,&m);
    reset();
    for(i=0;i<m;i++){
        fscanf(fi,"%d%d%d",&a,&b,&c);
        a--;
        b--;
        c=-c;
        nod[a][0].push_back(b);
        nod[a][1].push_back(c);
        nod[b][0].push_back(a);
        nod[b][1].push_back(c);
    }
    s=1;
    best[0][0]=0;
    best[0][1]=0;
    frq[0]=1;
    for(i=0;i<nod[0][0].size();i++){
        nd=nod[0][0][i];
        val=nod[0][1][i];
        h.push({val,nd});
        best[nd][0]=0;
        best[nd][1]=val;
    }
    while(s<n){
        nd=h.top().second;
        val=h.top().first;
        h.pop();
        if(best[nd][1]==val && frq[nd]==0){
            s++;
            sum+=val;
            frq[nd]=1;
            for(i=0;i<nod[nd][0].size();i++){
                nd2=nod[nd][0][i];
                val2=nod[nd][1][i];
                if(best[nd2][1]<val2 && frq[nd2]==0)
                {
                    best[nd2][1]=val2;
                    best[nd2][0]=nd;
                    h.push({val2,nd2});
                }
            }
        }
    }
    fprintf(fo,"%d\n",-sum);
    for(i=1;i<n;i++){
        fprintf(fo,"%d %d\n",i+1,best[i][0]+1);
    }
    fclose(fi);
    fclose(fo);
    return 0;
}