#include <cstdio>

using namespace std;

struct muchie{int vf,cost;};

muchie g[1000][1000];

int n,m,i,j,k,minimvf,tatavf,costmin,cmin[1000],tata[1000],x,y,c,uz[1000],start=1;

int v[1000],ctotal;

const int INF=1000000000;

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,&c);

        g[x][++v[x]].vf=y;
        g[x][v[x]].cost=c;
        g[y][++v[y]].vf=x;
        g[y][v[y]].cost=c;

    }
    uz[0]=1;
    uz[start]=1;
    for(i=1;i<=v[start];i++)

        cmin[g[start][i].vf]=g[start][i].cost;
    for(i=1;i<=n;i++)
    {
        if(cmin[i]==0)
            cmin[i]=INF;
        tata[i]=start;
    }
    tata[start]=0;
    cmin[start]=0;

    for(i=1;i<n;++i){

        while(uz[0]<n){

            costmin=INF;

            for(j=1;j<=n;j++)
                if(uz[j])
                {
                    for(k=1;k<=v[j];k++)
                        if(g[j][k].cost<costmin && uz[g[j][k].vf]==0)
                        {
                            costmin=g[j][k].cost;
                            minimvf=g[j][k].vf;
                            tatavf=j;
                        }
                }
            tata[minimvf]=tatavf;
            cmin[minimvf]=costmin;
            uz[minimvf]=1;
            uz[0]++;
        }
    }
    for(i=1;i<=n;++i){

        ctotal+=cmin[i];

    }
    printf("%d\n%d\n",ctotal,n-1);

    for(i=2;i<=n;++i){

        printf("%d %d\n",i,tata[i]);

    }
    return 0;
}