#include <stdio.h>
#include <algorithm>
#include <string.h>

#define max_n 200000
#define max_m 400000

using namespace std;

int n,m,i,j,x1,yy,c1,cost,rez,k,nr,q;
typedef struct costuri{
    int x,y,c;
};

costuri muchie[max_m];
int T[max_n],rang[max_n];
bool ok[max_n];
int sol[max_m][2];

inline bool cmp(const costuri &a,const costuri &b) {
    return a.c<b.c;
}

inline int multime(int nod) {
    if (T[nod]!=nod)
        T[nod]=multime(T[nod]);
    return T[nod];
}

void reuneste(int i,int j) {
    i=multime(i);
    j=multime(j);
    if (i==j) return;
    if (rang[i]<rang[j])
        T[i]=j;
    else
        T[j]=i;
    if (rang[i]==rang[j])
        rang[i]++;
}

int main () {
    freopen("apm.in","r",stdin);
    freopen("apm.out","w",stdout);
    scanf("%d%d",&n,&m);
    for (i=1; i<=m; i++) {
        scanf("%d%d%d",&x1,&yy,&c1);
        muchie[i].c=c1;
        muchie[i].x=x1;
        muchie[i].y=yy;
    }

    sort(muchie+1,muchie+m+1,cmp);

    for (i=1; i<=n; i++) {
        T[i]=i;
        rang[i]=0;
    }

    memset(ok,false,sizeof(ok));
    q=0;
    for (k=1; k<=m; k++) {
        i=muchie[k].x;
        j=muchie[k].y;
        cost=muchie[k].c;
        if (multime(i)!=multime(j)) {
            reuneste(i,j);
            rez+=cost;
            //printf("%d %d %d\n",i,j,cost);
            q++;
            sol[q][0]=i;
            sol[q][1]=j;
        }
    }
    printf("%d\n",rez);
    printf("%d\n",q);
    for (i=1; i<=q; i++)
        printf("%d %d\n",sol[i][0],sol[i][1]);
    return 0;
}