#include <iostream>
#include <fstream>
#define MAXIM 2000000000
#define MaxN 5000
using namespace std;
ifstream in("apm.in");
ofstream out("apm.out");
int ns,n,m,mat[MaxN][MaxN],viz[MaxN],T[MaxN],C[MaxN],minim;
void APM()
{
    int i,k,j,mini,r,q;
    ns=1;
    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;
        if(mat[a][b]!=0)
        {
            if(mat[a][b]>c)
            {
                mat[a][b]=c;
                mat[b][a]=c;
            }
        }
        else
        {
                mat[a][b]=c;
                mat[b][a]=c;
        }
    }
    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;
}