#include <cstdio>
#define NMAX 200001
#define MMAX 400001
using namespace std;

 int n,m,C[NMAX],Ord[NMAX-1],nrc,cmax;
 char cc[1000];
 struct muchie{

    int m1,m2,cost;

 }M[MMAX];

void citesc(){

    freopen("apm.in","r",stdin);
    freopen("apm.out","w",stdout);
    int ii,m11,m22,c;
    scanf("%d%d",&n,&m);

    for(int i=1;i<=m+1;i++){

    ii=0;
    m11=0,m22=0,c=0;
       bool ok = false;

        fgets(cc,1000,stdin);

            while(cc[ii] >= '0' && cc[ii]<= '9')
             m11 = m11*10 + (cc[ii++]- '0');
             ii++;

             while(cc[ii] >= '0' && cc[ii] <= '9')
             m22 = m22*10 + (cc[ii++] - '0');
             ii++;

             if(cc[ii] == '-'){

                ok = true;
                ii++;
             }

             while(cc[ii] >= '0' && cc[ii] <= '9')
             c = c*10 + (cc[ii++]- '0');


    if(i>1){
        if(ok == true)
                M[i-1].cost = -c;
             else
                M[i-1].cost = c;
    M[i-1].m1 = m11;
    M[i-1].m2 = m22;

}
    }


    for(int i=1;i<=n;i++)
    C[i] = i;
}

void quick_sort(int st, int dr){

    if(st<dr){
        int i = st , j = dr;
        muchie x = M[st];

            while(i<j){

                while(i<j && M[j].cost >= x.cost) j--;
                M[i] = M[j];
                while(i<j && M[i].cost <= x.cost) i++;
                M[j] = M[i];
            }
                M[i] =x;

    quick_sort(st,i-1);
    quick_sort(i+1,dr);
    }
}

void Kruskal(){

    int i,minim,maxim;

    for(i=1;nrc<n-1;i++){
        if(C[M[i].m1] != C[M[i].m2])
            Ord[++nrc] = i;
        if(C[M[i].m1] <= C[M[i].m2]){

            minim = C[M[i].m1];
            maxim = C[M[i].m2];
        }
        else{

            minim = C[M[i].m2];
            maxim = C[M[i].m1];
        }
            for(int k=1;k<=n;k++)
                if(C[k] == maxim)
                    C[k] = minim;
    }

    for(int i=1;i<=nrc;i++)
        cmax+=M[Ord[i]].cost;

}

void afisez(){

    printf("%d\n",cmax);
    printf("%d\n",nrc);
    for(int i=1;i<=nrc;i++)
        printf("%d %d\n",M[Ord[i]].m1,M[Ord[i]].m2);

}

int main(){

    citesc();
    quick_sort(1,m);
    Kruskal();
    afisez();
    return 0;
}