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

using namespace std;

ifstream fin("apm.in");
ofstream fout("apm.out");

struct Muchie
{
    int x, y, cost;
};

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

int n, m;
vector<Muchie> muchii;
int tata[200005];

int gaseste(int x)
{
    if (tata[x] == x)
        return x;
    return tata[x] = gaseste(tata[x]);
}

int main()
{
    fin >> n >> m;

    for (int i = 0; i < m; i++)
    {
        int u, v, c;
        fin >> u >> v >> c;
        muchii.push_back({u, v, c});
    }

    sort(muchii.begin(), muchii.end(), cmp);

    for (int i = 1; i <= n; i++)
    {
        tata[i] = i;
    }

    int cost_total = 0;
    vector<pair<int, int>> solutie;

    for (int i = 0; i < m; i++)
    {
        int sef_x = gaseste(muchii[i].x);
        int sef_y = gaseste(muchii[i].y);

        if (sef_x != sef_y)
        {
            cost_total += muchii[i].cost;
            solutie.push_back({muchii[i].x, muchii[i].y});

            tata[sef_y] = sef_x;
        }
    }

    fout << cost_total << "\n";
    fout << n - 1 << "\n";
    for (auto p : solutie)
    {
        fout << p.first << " " << p.second << "\n";
    }

    return 0;
}