#include <algorithm>
#include <iostream>
#include <vector>
#include <fstream>

using namespace std;
ifstream in("apm.in");
ofstream out("apm.out");
class Muchie
{
public:
    int x;
    int y;
    int cost = 0;
};

bool comparison(Muchie a, Muchie b)
{
    return a.cost < b.cost;
}

void Union1(int x, int y, int n, int repr[])
{
    int r1 = repr[x];
    int r2 = repr[y];
    for (int k = 1; k <= n; k++)
    {
        if (repr[k] == r2)
            repr[k] = r1;
    }
}

void v1() // doar cu reprezentant !!
{
    vector<Muchie> muchii;
    int n, m;
    in >> n >> m;
    for (int i = 1; i <= m; i++)
    {
        Muchie muchie;
        in >> muchie.x >> muchie.y >> muchie.cost;
        muchii.push_back(muchie);
    }
    sort(muchii.begin(), muchii.end(), comparison);
    int reprezentant[n + 1];
    for (int i = 1; i <= n; i++)
        reprezentant[i] = i;
    // for (auto it : muchii)
    //     cout << it.x << " " << it.y << " " << it.cost << endl;
    int nrmsel = 0;
    vector<Muchie> apm;
    int costTotal = 0;
    for (auto it : muchii)
    {
        if (reprezentant[it.x] != reprezentant[it.y])
        {
            apm.push_back(it);
            costTotal += it.cost;
            Union1(it.x, it.y, n, reprezentant);
            nrmsel += 1;
            if (nrmsel == n - 1)
                break;
        }
    }
    out << costTotal << endl;
    out << nrmsel << endl;
    for (auto it : apm)
        out << it.x << " " << it.y << endl;
}

int Repr2(int x, int tata[])
{
    if (tata[x] == 0)
        return x;
    tata[x] = Repr2(tata[x], tata);
    return tata[x];
}

void Union2(int x, int y, int n, int tata[], int h[])
{
    int rx, ry;
    rx = Repr2(x, tata);
    ry = Repr2(y, tata);
    if (h[rx] > h[ry])
    {
        tata[ry] = rx;
    }
    else
    {
        tata[rx] = ry;
        if (h[rx] == h[ry])
            h[rx] = h[ry] + 1;
    }
}

void v2() // cu vector de tati
{
    vector<Muchie> muchii;
    int n, m;
    in >> n >> m;
    for (int i = 1; i <= m; i++)
    {
        Muchie muchie;
        in >> muchie.x >> muchie.y >> muchie.cost;
        muchii.push_back(muchie);
    }
    sort(muchii.begin(), muchii.end(), comparison);
    int tata[n + 1], h[n + 1];
    for (int i = 1; i <= n; i++)
        tata[i] = h[i] = 0;
    int nrmsel = 0;
    int costTotal = 0;
    vector<Muchie> apm;
    for (auto it : muchii)
    {
        if (Repr2(it.x, tata) != Repr2(it.y, tata))
        {
            apm.push_back(it);
            costTotal += it.cost;
            Union2(it.x, it.y, n, tata, h);
            nrmsel += 1;
            if (nrmsel == n - 1)
                break;
        }
    }
    out << costTotal << endl;
    out << nrmsel << endl;
    for (auto it : apm)
    {
        out << it.x << " " << it.y << endl;
    }
}

int main()
{
    v2();
    return 0;
}