#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 Union(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;
    }
}

int main()
{
    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;
            Union(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;
    return 0;
}