#include<stdio.h>
int a[1501][1501],s[1501];
int main()
{
    int n,m,i,j,x,y,c,min,nr=0,k,t[1501],cost=0;
    freopen("apm.in","r",stdin);
    freopen("apm.out","w",stdout);
    scanf("%d%d",&n,&m);
    for(i=2;i<=n;i++)
        s[i]=1;
    for(i=1;i<=n;i++)
        for(j=1;j<=n;j++)
            if(i!=j)
            {
                a[i][j]=100001;
                a[j][i]=100001;
            }
    for(i=1;i<=m;i++)
    {
        scanf("%d%d%d",&x,&y,&c);
        a[x][y]=c;
        a[y][x]=c;
    }
    for(k=1;k<=n-1;k++)
    {
        min=100001;
        for(i=1;i<=n;i++)
            if(s[i])
                if(a[s[i]][i]<min)
                {
                    min=a[s[i]][i];
                    j=i;
                }
        t[j]=s[j];
        if(t[j]!=0)
            nr++;
		cost=cost+a[j][s[j]];
        s[j]=0;
        for(i=1;i<=n;i++)
            if(s[i]&&a[i][s[i]]>a[i][j])
                    s[i]=j;
         
    }
    printf("%d\n%d\n",cost,nr);
    for(i=2;i<=n;i++)
        if(t[i]!=0)
            printf("%d %d\n",t[i],i);
    return 0;
}