#include <fstream>
#include <algorithm>

#define MMAX 400001
#define NMAX 200001

using namespace std;

ifstream fin("apm.in");

ofstream fout("apm.out");

int n, m, nrm, cost_APM;

struct Muchie{
    int x, y;
    double cost;
};

Muchie G[MMAX];

int APM[NMAX], conex[MMAX];

void init();

bool crit(Muchie, Muchie);

int main()
{
    init();
    int i, j, cmic, cmare;
    for(i=1;i<=m;++i)
        if(conex[G[i].x]!=conex[G[i].y])
        {
                if(conex[G[i].x]<conex[G[i].y])
                {
                    cmic=conex[G[i].x];
                    cmare=conex[G[i].y];
                }
                else
                {
                    cmic=conex[G[i].y];
                    cmare=conex[G[i].x];
                }
                APM[++nrm]=i;
                cost_APM+=G[i].cost;
                for(j=1;j<=n;++j)
                    if(conex[j]==cmare)
                        conex[j]=cmic;
        }
    fout<<cost_APM<<'\n'<<nrm<<'\n';
    for(i=1;i<=n-1;++i)
        fout<<G[APM[i]].x<<" "<<G[APM[i]].y<<'\n';
    return 0;
}

void init()
{
    fin>>n>>m;
    int i;
    for(i=1;i<=m;++i)
        fin>>G[i].x>>G[i].y >>G[i].cost;
    for(i=1;i<=n;++i)
        conex[i]=i;
    sort(G+1,G+m+1, crit);
    /*
    for(i = 1 ;i<=m; ++i)
        fout<<G[i].x<<" "<<G[i].y<<" "<<G[i].cost<<"\n";
    */
}

bool crit(Muchie a, Muchie b)
{
    return (a.cost < b.cost);
}