#include <fstream>
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];
pair<int, int> P[400005];

void quicksort(int st, int dr)
{
    int i = st, j = dr, mij = A[(st + dr) / 2].cost;
    do {
        while (i < dr && A[i].cost < mij) ++i;
        while (j > st && A[j].cost > mij) --j;
        if (i <= j)
            swap(A[i++], A[j--]);
    } while (i <= j);
    if (st < j) quicksort(st, j);
    if (i < dr) quicksort(i, dr);
}

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;
    quicksort(1, 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";
}