#include <bits/stdc++.h>
using namespace std;
ifstream fin("apm.in");
ofstream fout("apm.out");

int n, m, r[200001], p[200001], cost;

struct muchie
{
    int a, b;
    int c;
};

bool operator<(const muchie &x, const muchie &y)
{
    return x.c > y.c;
}

vector<muchie> sol;
priority_queue<muchie> q;

void citire()
{
    fin >> n >> m;
    muchie x;
    for (int i = 1; i <= m; i++)
    {
        fin >> x.a >> x.b >> x.c;
        q.push(x);
    }
}

int parinte(int nod)
{
    if (p[nod] == 0)
        return nod;
    p[nod] = parinte(p[nod]);
    return p[nod];
}

void kruskal()
{
    while (!q.empty())
    {
        muchie crt = q.top();
        q.pop();
        int auxa, auxb;
        auxa = parinte(crt.a);
        auxb = parinte(crt.b);
        if (auxa != auxb)
        {
            if (r[auxa] < r[auxb])
            {
                swap(auxa, auxb);
            }
            p[auxb] = auxa;
            sol.push_back(crt);
            r[auxa] += r[auxb] + 1;
            cost += crt.c;
        }
    }
}

int main()
{
    citire();
    kruskal();
    fout << cost << "\n"
         << n - 1 << "\n";
    for (int i = 0; i < n - 1; i++)
    {
        fout << sol[i].a << " " << sol[i].b << "\n";
    }
    return 0;
}