#include <fstream>
using namespace std;
struct muchie
{
    int x,y,c;
}u[400002];
int main()
{
    ifstream f("apm.in");
    ofstream g("apm.out");
    int n,m,i,j,cost,k,viz[200002],nr,s[200002];
    f>>n>>m;
    for(i=1;i<=m;i++)
    {
        f>>u[i].x>>u[i].y>>u[i].c;
    }
    for(i=1;i<=m;i++)
    {
        for(j=i+1;j<=m;j++)
        {
            if(u[i].c>u[j].c)
            {
                swap(u[i],u[j]);
            }
        }
    }
    for(i=1;i<=n;i++)
    {
        viz[i]=i;
    }
    cost=0; k=0; i=1;
    while(k<n-1)
    {
        if(viz[u[i].x]!=viz[u[i].y])
        {
            cost=cost+u[i].c;
            k++;
            s[k]=i;
            nr=viz[u[i].y];
            for(j=1;j<=n;j++)
            {
                if(viz[j]==nr)
                    viz[j]=viz[u[i].x];
            }
        }
        i++;
    }
    g<<cost<<endl<<k<<endl;
    for(i=1;i<=k;i++)
    {
        g<<u[s[i]].x<<' '<<u[s[i]].y<<endl;
    }
}