#include <cstdio>
#include <algorithm>
using namespace std;
int n,m,i,j,k,s,x,y,nr,a[400001],c[200000][2];
struct muchie
{
    int x,y,cost;
}b[400001];
bool cmp(muchie A,muchie B)
{
    if(A.cost>B.cost)
        return 0;
    else
        return 1;
}
int main()
{
    freopen("apm.in","r",stdin);
    freopen("apm.out","w",stdout);
    scanf("%d %d\n",&n,&m);
    for(i=1;i<=m;i++)
        scanf("%d %d %d\n",&b[i].x,&b[i].y,&b[i].cost);
    for(i=1;i<=n;i++)
        a[i]=i;
    sort(b+1,b+m+1,cmp);
    nr=1;
    s=b[1].cost;
    k=1;
    c[1][0]=b[1].x;
    c[1][1]=b[1].y;
    a[b[1].x]=a[b[1].y];
    i=2;
    while(nr<n-1)
    {
        if(a[b[i].x]!=a[b[i].y])
        {
            x=a[b[i].x];
            y=a[b[i].y];
            for(j=1;j<=n;j++)
                if(a[j]==x)
                    a[j]=y;
            k++;
            c[k][0]=b[i].x;
            c[k][1]=b[i].y;
            s+=b[i].cost;
            nr++;
        }
        i++;
    }
    printf("%d\n%d\n",s,k);
    for(i=1;i<=k;i++)
        printf("%d %d\n",c[i][0],c[i][1]);
    return 0;
}