#include <fstream>

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



int n,m,c[10000][10000];
int s[1000],t[1000],capm=0,numar=0;

void cit()
{
    int i,j,a,b,co;
    fin>>n>>m;
    for(i=1;i<=n;i++)
    for(j=1;j<=n;j++)
            if(i!=j) c[i][j]=10000;

    for(i=1;i<=m;i++)
{
    fin>>a>>b>>co;
    c[a][b]=c[b][a]=co;
}
}

void prim(int r)
{ int i,k,j;
int minim;
s[r]=0;
t[r]=0;
for(i=1;i<=n;i++)
if(i!=r) s[i]=r;

for(k=2;k<=n;k++)
{   minim=10000;
    for(j=1;j<=n;j++)
    if(c[j][s[j]]<minim && s[j]!=0)
    {
        minim=c[j][s[j]];
        i=j;
    }
    t[i]=s[i];
    s[i]=0;
    capm+=minim;
    numar++;
    for(j=1;j<=n;j++)
    if(c[j][s[j]]>c[j][i] && s[j]!=0)
     s[j]=i;
}

}



int main()
{

int i;
cit();
prim(1);
fout<<capm<<endl<<numar<<endl;
for(i=1;i<=n;i++)
if(t[i]!=0) fout<<i<<" "<<t[i]<<endl;


    return 0;
}