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

using namespace std;

typedef struct edge {
    int p1, p2, cost;
} EDGE;

typedef struct re {
    int st, dr;
} R;

#define nmax 200001

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

int n, m;
int P[nmax], NR[nmax];
int nrm, rez, i;
EDGE E[nmax];
R V[nmax];

void init()
{
    for (i=1; i<=n; i++)
    {
        P[i] = i;
        NR[i] = 1;
    }
}

int root(int x)
{
    if (P[x] == x)
        return x;
    return root(P[x]);
}

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

void sortare()
{
    sort(E+1, E+m+1, cmp);
}

void citire()
{
    fin >> n >> m;

    init();

    for (i=1; i<=m; i++)
        fin >> E[i].p1 >> E[i].p2 >> E[i].cost;

    sortare();

}

void scrie()
{
    fout << rez << "\n";

    fout << nrm << "\n";

    for (i=1; i<=nrm; i++)
        fout << V[i].dr << " " << V[i].st << "\n";

}

void work()
{
    for (i=1; i<=m; i++)
    {
        int P1 = root(E[i].p1);
        int P2 = root(E[i].p2);

        if (P1 == P2)
            continue;

        if (NR[P1] >= NR[P2])
        {
            NR[P1] += NR[P2];
            P[P2] = P1;
        }
        else
        {
            NR[P2] += NR[P1];
            P[P1] = P2;
        }

        rez += E[i].cost;
        nrm++;

        V[nrm].st = E[i].p1;
        V[nrm].dr = E[i].p2;

        if (nrm == n-1)
            break;

    }

    scrie();

}

int main()
{

    citire();
    work();

    fin.close();
    fout.close();

    return 0;
}