#include <fstream>
#include <algorithm>
using namespace std;

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

int i, k, noduri, muchii, sef[200005], grad[200005], total;
struct muchie { int nod1, nod2, cost; } A[400005];
bool compara_muchii(muchie m1, muchie m2) { return m1.cost < m2.cost; };
pair<int, int> P[400005];

int ierarhie(int x)
{
    while (sef[x] != x)
        x = sef[x];

    return x;
}

void unificare(int a, int b)
{
    if (grad[a] <= grad[b])
    {
        sef[a] = b;
        if (grad[a] == grad[b])
            ++grad[b];
    }
    else
        sef[b] = a;
}

int main()
{
    fin >> noduri >> muchii;
    for (i = 1; i <= muchii; ++i)
        fin >> A[i].nod1 >> A[i].nod2 >> A[i].cost;
    for (i = 1; i <= noduri; ++i)
        sef[i] = i, grad[i] = 1;
    sort(A + 1, A + muchii + 1, compara_muchii);
    for (i = 1; i <= muchii; ++i)
    {
        int regeNod1 = ierarhie(A[i].nod1), regeNod2 = ierarhie(A[i].nod2);
        if (regeNod1 != regeNod2)
        {
            unificare(regeNod1, regeNod2);
            P[++k].first = A[i].nod1;
            P[k].second = A[i].nod2;
            total += A[i].cost;
        }
    }

    fout << total << "\n" << k << "\n";
    for (i = 1; i <= k; ++i)
        fout << P[i].second << ' ' << P[i].first << "\n";
}