#include <fstream>
#include <vector>
#include <algorithm
using namespace std
ifstream f("apm.in");
ofstream g("apm.out");
int n, m, sol, tata[200005], adan[200005];
bool viz[200005];
vector<pair<int, pair<int, int>>> G;
vector<pair<int, int>> sol_muchii;
int rad(int x)
{
    if (tata[x] == x)
        return x;
    int rad = rad(tata[x]);
    tata[x] = rad;
    return rad;
}
void reuniune(int x, int y)
{
    int rad1 = rad(x), rad2 = rad(y);
    if (adan[rad1] > adan[rad2])
        tata[rad2] = rad1;
    else
    {
        tata[rad1] = rad2;
        adan[rad2] = max(adan[rad2], adan[rad1] + 1);
    }
}
void prelucrare()
{
    for (auto &muchie: G)
    {
        if (rad(muchie.second.first) == rad(muchie.second.second))
            continue;
        sol += muchie.first;
        sol_muchii.push_back(muchie.second);
        reuniune(muchie.second.first, muchie.second.second);
    }
}
int main()
{
    f >> n >> m;
    int x, y, c;
    for (int i = 0; i < m; i++)
    {
        f >> x >> y >> c;
        G.push_back({c, {x, y}});
    }
    sort(G.begin(), G.end());
    for (int i = 1; i <= n; i++)
        tata[i] = i;
    prelucrare();
    g << sol << '\n' << sol_muchii.size();
    for (auto &muchie: sol_muchii)
        g << '\n' << muchie.first << ' ' << muchie.second;
    return 0;
}