#include <cstdio>
#include <algorithm>
#include<vector>

using namespace std;

int i,aux,n,k,j,p,s,unu,t,m,doi,x,mini,maxi,sol,cont,viz[100010],y,cost,a[100010],b[100010];

struct coada
{
    int x,y,cost;
}c[200010];

bool cmp(coada i,coada j)
{
    return i.cost<j.cost;
}

int main()
{
    freopen ("apm.in","r",stdin);
    freopen ("apm.out","w",stdout);
    scanf("%d%d",&n,&m);
    for(i=1;i<=m;i++)
    {
        scanf("%d %d %d",&x,&y,&cost);
        c[i].x=x;
        c[i].y=y;
        c[i].cost=cost;
    }

    sort(c+1,c+m+1,cmp);
    for(i=1;i<=n;i++)
    {
        viz[i]=i;
    }

    for(i=1;i<=m;i++)
    {
       // printf("%d %d %d\n",c[i].x,c[i].y,c[i].cost);
    }
    cont=0;
    k=0;
    while(cont<=n-1)
    {
        k++;
        if(viz[c[k].x]!=viz[c[k].y])
        {
            cont++;
            a[cont]=c[k].x;
            b[cont]=c[k].y;
            if(viz[c[k].x]>viz[c[k].y])
            {
                maxi=viz[c[k].x];
                mini=viz[c[k].y];
            }
            else
            {
                mini=viz[c[k].x];
                maxi=viz[c[k].y];
            }
            for(i=1;i<=n;i++)
            {
                if(viz[i]==maxi)
                {
                    viz[i]=mini;
                }
            }
            s=s+c[k].cost;
        }

    }
    printf("%d\n%d\n",s,cont-1);
    for(i=1;i<=cont-1;i++)
    {
        printf("%d %d\n",a[i],b[i]);
    }

}