#include <algorithm>
#include <iostream>
#include <fstream>
#include <vector>

using namespace std;

struct muchie
{
    int extrS, extrD, cost;
};
vector<muchie>grafN, arb_min;
int n, arb[105];

bool comp(muchie a, muchie b)
{
    return a.cost < b.cost;
}

int findArb(int nod)
{
   if (nod == arb[nod]){
        return nod;
   }
    return findArb(arb[nod]);
}

int main()
{
    ifstream f("apm.in");
    ofstream g("apm.out");

    int m, i, x, y, c, cost_tot = 0;
    f>>n>>m;
    while(f>>x>>y>>c)
    {
        grafN.push_back({x, y, c});
    }
    sort(grafN.begin(), grafN.end(), comp);

    for(i=1; i<=n; i++)
    {
        arb[i] = i;
    }

    for(i=0; i<grafN.size(); i++)
    {
        int parU = findArb(grafN[i].extrS);
        int parV = findArb(grafN[i].extrD);
        if(parU != parV)
        {
            arb[parU] = arb[parV];
            arb_min.push_back(grafN[i]);
            cost_tot += grafN[i].cost;
        }
    }
    g<<cost_tot<<"\n"<<n-1<<"\n";
    for(i=0; i<arb_min.size(); i++)
    {
        g<<arb_min[i].extrS<<" "<<arb_min[i].extrD<<"\n";
    }

    return 0;
}