#include <cstdio>
#include <vector>
#define MaxN 200009
#define MaxM 400009
#define MaxC 1009

using namespace std;

vector <int> v[MaxN],cs[MaxN],x,y,nod;
int n,m,C,uz[MaxN];

void cit()
{
    int i,x,y,c;
    freopen("apm.in","r",stdin);
    scanf("%d%d",&n,&m);
    for(i=1;i<=m;i++)
    {
        scanf("%d%d%d",&x,&y,&c);
        v[x].push_back(y); cs[x].push_back(c);
        v[y].push_back(x); cs[y].push_back(c);
    }
}

void cauta(int &xi,int &yi,int &s)
{
    int min=MaxC,i,j,X,Y;
    for(i=0;i<nod.size();i++)
    {
        X=nod[i];
        for(j=0;j<v[X].size();j++)
        {
            Y=v[X][j];
            if(!uz[Y] && cs[X][j]<min)
                xi=X, yi=Y, min=cs[X][j];
        }
    }
    s=min;
}

void sol()
{
    int nr,xi,yi,s;
    uz[1]=1; nr=1;
    nod.push_back(1);
    while(nr<n)
    {
        cauta(xi,yi,s);
        uz[yi]=1; nod.push_back(yi);
        C+=s;
        x.push_back(xi); y.push_back(yi);
        nr++;
    }
}



void afis()
{
    int i;
    freopen("apm.out","w",stdout);
    printf("%d\n",C);
    printf("%d\n",n-1);
    for(i=0;i<x.size();i++)
        printf("%d %d\n",x[i],y[i]);
}

int main()
{
    cit();
    sol();
    afis();
    return 0;
}