#include <iostream>
#include <cstdio>
#include <algorithm>

using namespace std;

int n,m,sef[200005];

struct MUCHIE
{
    int x,y,c;
};
MUCHIE v[400005], sol[200005];

bool cmp(MUCHIE a, MUCHIE b)
{
    if(a.c<b.c)
        return 1;
    else
        return 0;
}

int sef_suprem(int a)
{
    if(sef[a]==a)
        return a;
    else
        return sef_suprem(sef[a]);
}
void unire(int sefa, int sefb)
{
    sef[sefb] = sefa;
}

int main()
{
    freopen("apm.in","r",stdin);
    freopen("apm.out","w",stdout);
    int i,u,p,cost,k,j;
    scanf("%d%d",&n,&m);
    for(i=1; i<=m; i++)
    {
        scanf("%d %d %d",&p,&u,&cost);
        v[i].x=p;
        v[i].y=u;
        v[i].c=cost;
    }
    sort(v+1,v+m+1,cmp);
    for(i=1; i<=n; i++)
        sef[i]=i;
    k=n-1;
    //printf("%d",cost);
    i=1;
    j=1;
    cost = 0;
    while(k)
    {
        int sefa = sef_suprem(v[i].x);
        int sefb = sef_suprem(v[i].y);
        if(sefa != sefb)
        {
            cost=cost+v[i].c;
            unire(sefa, sefb);
            k--;
            sol[j].x=v[i].x;
            sol[j].y=v[i].y;
            j++;
        }
        i++;
    }
    printf("%d\n%d\n",cost,n-1);
    for(i=1; i<n; i++)
        printf("%d %d\n",sol[i].x,sol[i].y);
//    for(i=1;i<=m;i++)
//        printf("%d %d %d\n",v[i].x,v[i].y,v[i].c);
    return 0;
}