#include <fstream>
#define DMAX 1000
#define INF 20000000

using namespace std;
ifstream fin("apm.in");
ofstream fout("apm.out");

struct vecin
{
int vf, c;
};
vecin L[DMAX][DMAX];
int n, m, vf_st=1, costapm;
int cmin[DMAX], prec[DMAX];
bool Z[DMAX];

void read();
void init();
void Prim();
void write();

int main()
{
read();
Prim();
write();
return 0;
}

void Prim()
{
int i, j, vfmin;
init();
for (i=1; i<=n-1; ++i)
    {
        vfmin=n+1;
        for (j=2; j<=n; j++)
            if (cmin[vfmin]>cmin[j] && !Z[j])
                vfmin=j;
        Z[vfmin]=1;
        costapm+=cmin[vfmin];
        for (j=1; j<=L[vfmin][0].vf; ++j)
            if (!Z[L[vfmin][j].vf] && L[vfmin][j].c<cmin[L[vfmin][j].vf])
                {
                    cmin[L[vfmin][j].vf]=L[vfmin][j].c;
                    prec[L[vfmin][j].vf]=vfmin;
                }
    }
}

void init()
{
int i, j;

cmin[n+1]=INF;
for (i=1; i<=n; ++i)
    {
        prec[i]=vf_st;
        for (j=1; j<=L[vf_st][0].vf; ++j)
            if (L[vf_st][j].vf==i)
                cmin[i]=L[vf_st][j].c;
        if (!cmin[i]) // daca nu exista muchie de la vf_st la i
            cmin[i]=INF;
    }
prec[vf_st]=0; cmin[vf_st]=0; Z[vf_st]=1;
}

void read()
{
int i, x, y, c;

fin>>n>>m;
for (i=1; i<=m; i++)
    {
        fin>>x>>y>>c;
        L[x][++L[x][0].vf].vf=y;
        L[x][L[x][0].vf].c=c;
        L[y][++L[y][0].vf].vf=x;
        L[y][L[y][0].vf].c=c;
    }
}

void write()
{
int i;

fout<<costapm<<'\n'<<n-1<<'\n';
for (i=1; i<=n; i++)
    if (i!=vf_st)
        fout<<i<<' '<<prec[i]<<'\n';
fout.close();
}