#include <iostream>
#include <fstream>

using namespace std;

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

const int MAX=4e5+5;
int n,m,viz[MAX],sol[MAX],cost,mc;
struct M
{
    int a,b,cost;
}mch[MAX];

int main()
{
    fin >> n >> m;
    for(int i=1;i<=m;i++)
    {
        fin >> mch[i].a >> mch[i].b >> mch[i].cost;
        if(!mc || mch[i].cost<mch[mc].cost)
            mc=i;
    }
    sol[1]=mc;
    cost=mch[mc].cost;
    viz[mch[mc].a]=viz[mch[mc].b]=1;
    for(int i=2;i<n;i++)
    {
        mc=0;
        for(int j=1;j<=m;j++)
            if(viz[mch[j].a]^viz[mch[j].b] && (!mc || mch[j].cost<mch[mc].cost))
                mc=j;
        sol[i]=mc;
        cost+=mch[mc].cost;
        viz[mch[mc].a]=viz[mch[mc].b]=1;
    }
    fout << cost << '\n' << n-1 << '\n';
    for(int i=1;i<n;i++)
        fout << mch[sol[i]].a << " " << mch[sol[i]].b << '\n';
    return 0;
}