#include <fstream>
using namespace std;
ifstream f("apm.in");
ofstream g("apm.out");
int m,n,x,y,cost,ms,viz[1001],A[1001],i,j,mini,maxi;
struct muchie {int x,y,c;}v[1001];
int main()
{
    f>>n>>m;
    for(i=1;i<=m;i++)
    {
        f>>v[i].x>>v[i].y>>v[i].c;
    }
    for(i=1;i<m;i++)
        for(j=i+1;j<=m;j++)
        {
            if(v[i].c>v[j].c) swap(v[i],v[j]);
        }
    ms=0;
    for(i=1;i<=n;i++)
        viz[i]=i;
    for(i=1;ms<n-1;i++)
    {

        if (viz[v[i].x]!=viz[v[i].y])
        {
            A[++ms]=i;
            if(viz[v[i].x]<viz[v[i].y])
            {
                mini=viz[v[i].x];
                maxi=viz[v[i].y];
            }
            else
            {
                mini=viz[v[i].y];
                maxi=viz[v[i].x];
            }
            for(j=1;j<=n;j++)
                if(viz[j]==maxi) viz[j]=mini;
        }
    }
    for(i=1;i<n;i++)
    {

        cost+=v[A[i]].c;
    }
    g<<cost<<endl;
    g<<n-1<<endl;
    for(i=1;i<n;i++)
    {
        g<<v[A[i]].x<<" "<<v[A[i]].y<<endl;
    }

    return 0;
}