#include <iostream>
#include <fstream>
#define MAXIM 2000
using namespace std;
ifstream in("apm.in");
ofstream out("apm.out");
int ns,n,m,mat[1501][1501],viz[1501],T[1501],C[1501];
long int minim;
void APM()
{
    int i,k,j,mini,r,q;
    viz[ns]=1;
    for(k=1;k<n;k++)
    {
        mini=MAXIM;
        for(i=1;i<=n;i++)
            for(j=1;j<=n;j++)
                if(viz[j]==0)
                    if(mat[i][j]!=0)
                        if(viz[i]==1)
                            if(mat[i][j]<mini)
                                {
                                    mini=mat[i][j];
                                    r=j;
                                    q=i;
                                }
        viz[r]=1;
        T[r]=q;
        C[r]=mini;
    }
}
int main()
{ int a,b,c,i;
in>>n>>m;
for(i=1;i<=m;i++)
{
    in>>a>>b>>c;
    mat[a][b]=c;
    mat[b][a]=c;
}
ns=1;
in.close();
APM();
for(i=1;i<=n;i++)
{minim=minim+C[i];

}
out<<minim<<"\n";
out<<n-1<<"\n";
for(i=2;i<=n;i++)
    out<<i<<" "<<T[i]<<"\n";

        return 0;
}