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

struct Edge{
    int x, y, cost;

    bool operator< (const Edge& x) const
    {
        return cost < x.cost;
    }
};

void ReadData();
void Kruskal();
void Union(int r1, int r2);
int Find(int x);
void Write();

int n, m, rez, cnt;
std::vector<int> t, h;
std::vector<Edge> G, sol;

int main()
{
    ReadData();
    Kruskal();
    Write();
}

void ReadData()
{
    std::ifstream fin("apm.in");
    fin >> n >> m;

    t = std::vector<int>(n);
    h = std::vector<int>(n);

    int x, y, cost;

    for (int i = 0; i < m; ++i)
    {
        fin >> x >> y >> cost;
        G.push_back({x, y, cost});
    }

    fin.close();
}

void Kruskal()
{
    for (int i = 1; i <= n; ++i)
        t[i] = i;

    std::sort(G.begin(), G.end());

    for (const auto& m : G)
    {
        int r1 = Find(m.x);
        int r2 = Find(m.y);

        if (r1 == r2)
            continue;

        Union(r1, r2);

        rez += m.cost;
        sol.push_back(m);

        cnt++;
        if (cnt == n - 1)
            break;
    }
}

int Find(int x)
{
    if (x == t[x])
        return x;
    return t[x] = Find(t[x]);
}

void Union(int r1, int r2)
{
    if (h[r1] > h[r2])
        t[r2] = r1;
    else
    {
        t[r1] = r2;
        if (h[r1] == h[r2])
            h[r2]++;
    }
}

void Write()
{
    std::ofstream fout("apm.out");

    fout << rez << '\n' << cnt << '\n';

    for (auto it = sol.begin(); it != sol.end(); ++it)
        fout << it->y << ' ' << it->x << '\n';// << it->cost << '\n';

    fout.close();
}