#include <stdio.h>
#define INF 1000000000
long n,x,i,j,k,c,l,cost[1000][1000],s[1000],min,m,vsoli[1000],vsolj[1000];
int main()
{
    freopen ("apm.in","r",stdin);
    freopen ("apm.out","w",stdout);
    scanf("%ld %ld",&n,&m);
    //initializare cost
    for (i=1;i<=n;++i)
        for (j=1;j<=n;++j)
            if (i==j)
               cost[i][j]=0;
            else
                cost[i][j]=INF,cost[j][i]=INF;
    //introducere cost
    for (k=1;k<=m;++k){
        scanf("%ld %ld %ld\n",&i,&j,&c);
        cost[i][j]=c,cost[j][i]=c;
        }
    c=0;    
    //rezolvare O(n^2)    
        
    for(i=2;i<=n;++i)s[i]=1;
    
    for (k=1;k<n;++k){
        min=INF;
        for (i=1;i<=n;++i)
            if (s[i])
               if (min>cost[s[i]][i]){
                  min=cost[s[i]][i];
                  j=i;
                  }
        vsoli[++x]=s[j];vsolj[x]=j;c+=cost[j][s[j]];
        //printf("%ld %ld %ld\n",s[j],j,cost[j][s[j]]);
        for (i=1;i<=n;++i)
            if (s[i] && cost[i][s[i]]>cost[i][j])
               s[i]=j;
            s[j]=0;
        }
    printf("%ld\n%ld\n",c,x);
    for(i=1;i<=x;++i)printf("%ld %ld\n",vsoli[i],vsolj[i]);
    return 0;
}