#include <stdlib.h>
#include <stdio.h>
 
typedef struct muchie{
    int n1,n2,cost;
}muchie;

struct muchie graf[400008], apm[200008];
int t[200008], h[200008];

int cmp(muchie a, muchie b)
{
    return(a.cost < b.cost);
}
 
int root(int x)
{
    while (t[x]!=0)
        x = t[x];
    return x;
}
 
int main()
{
    FILE *f,*g;
    f=fopen("apm.in","r");
    g=fopen("apm.out","w");

    int n,m,i;
    fscanf(f,"%d %d", &n,&m);
 
    for(i=1;i<=m;i++)
    {
        fscanf(f,"%d %d %d", &graf[i].n1, &graf[i].n2, &graf[i].cost);
    }
 
    qsort(graf,m,sizeof(muchie),&cmp);
 
    int c[200000];
    for(i=1;i<=n;i++)
    {
        c[i]=i;
    }
 
    int ct=0, cost=0;;
 
    for(i=1;i<=m;i++)
    {
        int x=graf[i].n1;
        int y=graf[i].n2;
        int rx = root(x);
        int ry = root(y);
        if(rx!=ry){
            ct++;
            apm[ct]=graf[i];
            cost+=graf[i].cost;
            if (h[rx] > h[ry])
                t[ry] = rx;
            else
                if (h[rx] < h[ry])
                    t[rx] = ry;
                else
                {
                    t[ry] = rx;
                    h[rx]++;
                }
        }
        if(ct==n-1){
            break;
        }
    }
    fprintf(g,"%d\n%d\n",cost, n-1);
    for(i=1;i<=ct;i++)
        fprintf(g,"%d %d\n", apm[i].n1, apm[i].n2);

    return 0;
}