#include <fstream>
#define NMAX 2000
#define INF 100000

using namespace std;


FILE *fin,*fout;

int n,m,x;
int M[NMAX][NMAX];
int cmin[NMAX];
int use[NMAX];
int p[NMAX];

int select();
void refacere(int);

int main()
{
    int i,a,b,c;
    int S=0;
    fin=fopen("apm.in","r");
    fout=fopen("apm.out","w");
    fscanf(fin,"%d%d",&n,&m);
    for(i=1;i<=m;i++)
    {
        fscanf(fin,"%d%d%d",&a,&b,&c);
        M[a][b]=c;
        M[b][a]=c;
    }
    use[1]=1;
    for(i=2;i<=n;i++)
    {
        if(M[1][i]!=0)
            cmin[i]=M[1][i];
        else cmin[i]=INF;
        p[i]=1;
    }
    for(i=1;i<n;i++)
    {
        x=select();
        use[x]=1;
        refacere(x);
    }

    for(i=1;i<=n;i++)
    {
        S+=cmin[i];
    }
    fprintf(fout,"%d\n%d\n",S,n-1);
    for(i=1;i<=n;i++)
        if(p[i])
            fprintf(fout,"%d %d\n",i,p[i]);
    return 0;
}

void refacere(int x)
{
    int i;
    for(i=1;i<=n;i++)
        if(M[x][i]<cmin[i] && M[x][i] && !use[i])
        {
            cmin[i]=M[x][i];
            p[i]=x;
        }
}

int select()
{
    int i,minim=INF,unde=0;
    for(i=1;i<=n;i++)
        if(!use[i])
            if(cmin[i]<minim)
            {
                minim=cmin[i];
                unde=i;
            }
    return unde;
}