#include <fstream>
#include <algorithm>
#define DMAX 200001
#define MMAX 400001
using namespace std;

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

struct pack muchii[MMAX];
int APM[DMAX];//indicii muchiilor selectate
int cost_APM, lg_APM;
int n, m, conex[DMAX];

bool cmp (struct pack, struct pack);
void citire();
void kruskal();
void afisare();

int main()
{
    citire();
    sort (muchii+1, muchii+m+1, cmp);
    kruskal();
    afisare();
    return 0;
}

void citire()
{
    ifstream fin ("apm.in");
    int i;
    fin>>n>>m;
    for (i=1; i<=m; ++i)
        fin>>muchii[i].x>>muchii[i].y>>muchii[i].cost;

    for (i=1; i<=n; ++i)
        conex[i]=i;
    fin.close();
    return;
}

bool cmp (struct pack a, struct pack b)
{
    return a.cost<b.cost;
}

void kruskal()
{
    int i, j, minimus, maximus;
    for (i=1; i<=m; ++i)
    {
        //pot selecta muchia i?
        if (conex[muchii[i].x]!=conex[muchii[i].y])
        {
            cost_APM+=muchii[i].cost;
            APM[++lg_APM]=i;

            minimus=conex[muchii[i].x]; maximus=conex[muchii[i].y];
            if (maximus<minimus)
                {
                    minimus=conex[muchii[i].y];
                    maximus=conex[muchii[i].x];
                }
            for (j=1; j<=n; ++j)
                if (conex[j]==maximus)
                    conex[j]=minimus;
        }
    }
    return;
}

void afisare()
{
    ofstream fout ("apm.out");
    int i;
    fout<<cost_APM<<"\n"<<lg_APM<<"\n";
    for (i=1; i<=n-1; ++i)
        fout<<muchii[APM[i]].x<<" "<<muchii[APM[i]].y<<"\n";
    fout.close();
    return;

}