#include <algorithm>
#include <fstream>
#include <vector>
using namespace std;
ifstream f("apm.in");
ofstream g("apm.out");
int n,m;
struct muchie
{
    int x,y,c;
};

vector<muchie> U;
vector<muchie> solutie;

void citire()
{
    muchie aux;
    f >> n >> m;
    for(int i=1;i<=m;i++)
    {
        f >> aux.x >> aux.y >> aux.c;
        U.push_back(aux);
    }
    f.close();
}

bool comparareCost(const muchie &a, const muchie &b)
{
    return a.c < b.c;
}

int main()
{
    int k, ct, j,i, L[200001], arb1, arb2;
    citire();
    sort(U.begin(), U.end(), comparareCost);
    ct = 0;
    k = 0;
    for(i=1;i<=n;i++) L[i] = i;
    i = 0;
    while(k<n-1)
    {
        if(L[U[i].x] != L[U[i].y])
        {
            k++;
            arb1=L[U[i].x];
            arb2=L[U[i].y];
            ct = ct + U[i].c;
            solutie.push_back(U[i]);
            for(j=1;j<=n;j++) if (L[j] == arb2 ) L[j] = arb1;
        }
        i++;
    }
    g << ct << '\n' << n-1 << '\n';
    for(i=0;i<n-1;i++)
    {
        g << solutie[i].x << ' ' << solutie[i].y << '\n';
    }

    g << '\n';
    g.close();
    return 0;
}