#include<stdio.h>
#define nmax 200001
#define mmax 400001

struct muchie
{
    int x,y,cost,valid;
} v[mmax];

int t[nmax],n,m,sum;

void sort(int,int);

int up(int k)
{
    for(;t[k];k=t[k]);
    return k;
}

int interogare(int a,int b)
{
    int A=up(a);
    while (t[a])
        {
            t[a]=A;
            a=t[a];
        }
    int B=up(b);
    while (t[b])
        {
            t[b]=B;
            b=t[b];
        }
        
    if (A==B)
        return 0;
    else
        return 1;
}

void kruskal()
{
    for(int i=1;i<=m;++i)
        if (interogare(v[i].x,v[i].y))
            {
                v[i].valid=1;
                sum+=v[i].cost;
                t[up(v[i].y)]=up(v[i].x);
            }
}

int main()
{
    freopen("apm.in","r",stdin);
    freopen("apm.out","w",stdout);
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;++i)
        scanf("%d%d%d",&v[i].x,&v[i].y,&v[i].cost);
    sort(1,m);
    kruskal();
    printf("%d\n%d\n",sum,n-1);
    for(int i=1;i<=m;++i)
        if (v[i].valid)
            printf("%d %d\n",v[i].x,v[i].y);
    return 0;
}

void sort(int st,int dr)
{
    int poz=st-1;
    for(int i=st;i<=dr;++i)
        if (v[i].cost<=v[dr].cost)
            {
                muchie aux=v[i];
                v[i]=v[++poz];
                v[poz]=aux;
            }
    if (st<poz-1)
        sort(st,poz-1);
    if (poz+1<dr)
        sort(poz+1,dr);
}