#include <cstdio>
#include <string.h>
#include <algorithm>
#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];

inline bool order(const muchie A, const muchie B){

    if(A.cost == B.cost){
        if(A.m1 == B.m1)
             return A.m2 < B.m2;
             return A.m1 < B.m1;
    }

return A.cost < B.cost;
}

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;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' && ii < strlen(cc))
             c = c*10 + (cc[ii++]- '0');



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


    }


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

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();
    sort(M+1,M+1+m,order);
    Kruskal();
    afisez();
    return 0;
}