#include <bits/stdc++.h>

using namespace std;
int tata[200001], n, i, j, card[200001],  x, y, m, raspuns, contor, str1, str2;
struct muchie
{
    int x, y, val;
}muchii[400001];
struct data
{
    int x, y;
}pereche[200000];
struct cmp
{
    bool operator () (const muchie &a, const muchie &b)
    {
        return a.val<b.val;
    }
};
int stapan (int nod)
{
    int rege = nod, copie;
    while (tata[rege] != rege)
        rege = tata[rege];
    while (tata[nod] != nod)
    {
        copie = nod;
        nod = tata[nod];
        tata[copie] = rege;
    }
    return rege;
}
void unire (int a, int b)
{
    int st1 = stapan(a), st2 = stapan(b);
    if (st2 == st1)
        return ;
    if (card[st1] > card[st2])
    {
        card[st1]+=card[st2];
        tata[st2] = st1;
    }
    else
    {
        card[st2] += card[st1];
        tata[st1] = st2;
    }
}
int main()
{
    ofstream fout ("apm.out");
    ifstream fin ("apm.in");
    fin >> n >> m;
    for (i=0; i<m; ++i)
        fin >> muchii[i].x >> muchii[i].y >> muchii[i].val;
    for (i=1; i<=n; ++i)
    {
        tata[i] = i;
        card[i] = 1;
    }
    sort (muchii, muchii+m, cmp());
    for (i = 0; i<m; ++i)
    {
        x = muchii[i].x;
        y = muchii[i].y;
        str1 = stapan(x);
        str2 = stapan(y);
        if (str1 != str2)
        {
            pereche[contor].x = x;
            pereche[contor].y = y;
            ++contor;
            raspuns+=muchii[i].val;
            unire(str1, str2);
        }
    }
    fout << raspuns << '\n';
    fout << contor << '\n';
    for (i=0; i<contor; ++i)
        fout << pereche[i].x << " " << pereche[i].y << '\n';
    return 0;
}