#include <fstream>
#include <algorithm>

using namespace std;

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

int N, M, nrsol;
int sum;
int T[200005];

struct noduri
{
    int nod1, nod2, cost;
};
noduri V[200005], sol[200005];

bool cmp(noduri A, noduri B)
{
    return A.cost < B.cost;
}

void update(int x, int y)
{
    if (x > y)
        swap(x, y);
    T[x] = y;
}

int query(int x)
{
    if (T[x] == x)
        return x;
    T[x] = query(T[x]);
    return T[x];
}

int main()
{
    fin >> N >> M;
    for (int i = 1; i <= M; ++i)
        fin >> V[i].nod1 >> V[i].nod2 >> V[i].cost;

    sort(V + 1, V + M + 1, cmp);

    for (int i = 1; i <= N; ++i)
        T[i] = i;
    for (int i = 1; i <= M; ++i)
    {
        int rad1 = query(V[i].nod1);
        int rad2 = query(V[i].nod2);
        if (rad1 != rad2)
        {
            sum += V[i].cost;
            update(rad1, rad2);
            sol[++nrsol] = V[i];
        }
    }

    fout << sum << '\n';
    fout << nrsol << '\n';
    for (int i = 1; i <= nrsol; ++i)
        fout << sol[i].nod1 << ' ' << sol[i].nod2 << '\n';

    fin.close();
    fout.close();
    return 0;
}