#include <bits/stdc++.h>
#define minf -2000000000
#define BLen 10000

char BUFF[BLen];

FILE*fi;

int k=0;

int cit(){
    int nr=0,q=1;
    while((BUFF[k]<'0' || BUFF[k]>'9') && BUFF[k]!='-'){
        if(++k==BLen){
            fread(BUFF,1,BLen,fi);
            k=0;
        }
    }
    if(BUFF[k]=='-'){
        q=-1;
        k++;
    }
    while(BUFF[k]>='0' && BUFF[k]<='9'){
        nr=nr*10+BUFF[k]-'0';
        if(++k==BLen){
            fread(BUFF,1,BLen,fi);
            k=0;
        }
    }
    return nr*q;
}

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*fo;
    fi=fopen("apm.in","r");
    fo=fopen("apm.out","w");
    fread(BUFF,1,BLen,fi);
    k=0;
    n=cit();
    m=cit();
    reset();
    for(i=0;i<m;i++){
        a=cit();
        b=cit();
        c=cit();
        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);
    }
    printf("1");
    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%d\n",-sum,n-1);
    for(i=1;i<n;i++){
        fprintf(fo,"%d %d\n",i+1,best[i][0]+1);
    }
    fclose(fi);
    fclose(fo);
    return 0;
}