#include<stdio.h>
#define nmax 1001
#define mmax 1001

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

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

void schimb(int i,int j)
{
    for(int k=1;k<=n;++k)
        if (viz[k]==j)   
	    viz[k]=i;
}

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);
}

void kruskal()
{
    for(int i=1;i<=n;++i)
        viz[i]=i;
    
    for(int i=1;i<=m;++i)
        if (viz[v[i].x]!=viz[v[i].y])
            {
                v[i].valid=1;
                sum+=v[i].cost;
                schimb(viz[v[i].x],viz[v[i].y]);
            }
}

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;
}