#include <cstdio>
#include <algorithm>
using namespace std;

struct muchie{ int x,y,c; }u[400002];
int n,m,rad[200002],cost;

bool cmp(muchie a,muchie b){ return a.c < b.c; }

int tata(int x){
    if(x != rad[x])rad[x] = tata(rad[x]);
    return rad[x];
}


void apm(){
    int i = 0;
    for(int k=1;k<=n;k++)rad[k] = k;
    for(int k=1;k<n;k++)
    {
        while(tata(u[i].x) == tata(u[i].y)) i++;
        cost+=u[i].c;
        u[i].c=-1;
        rad[tata(u[i].x)]=tata(u[i].y);
        i++;
    }
}

int main(){
    freopen("apm.in","r",stdin);
    freopen("apm.out","w",stdout);
        scanf("%d %d",&n,&m);

        for(int i=0;i<m;i++)scanf("%d %d %d",&u[i].x,&u[i].y,&u[i].c);

        sort(u,u+m,cmp);
     //   for(int i=0;i<m;i++)printf("%d\n",u[i].c);

        apm();

        printf("%d\n",cost);
        printf("%d\n",n-1);
        for(int i=0;i<m;i++)
        if(u[i].c == -1)printf("%d %d\n",u[i].x,u[i].y);

    return 0;
}