#include <fstream>
#include <algorithm>
#include <vector>
#define NMAX 200005

using namespace std;

ifstream f("apm.in");
ofstream g("apm.out");

int i, n, m, ans = 0, x, y, c, father[NMAX], used = 0;
vector < pair < int, int > > sol;

struct apm
{
    int x, y, c;
};
apm v[2 * NMAX];

int get_father(int node)
{
    if (node != father[node])
        node = get_father(father[node]);
    return node;
}

void unite(int x, int y)
{
    father[get_father(x)] = get_father(y);
}

bool cmp(apm a, apm b)
{
    return a.c < b.c;
}

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

    for (i = 1; i <= m; ++ i)
    {
        f >> v[i].x >> v[i].y >> v[i].c;
        father[i] = i;
    }

    sort(v + 1, v + m + 1, cmp);

    for (i = 1; i <= m; ++ i)
    {
        x = v[i].x;
        y = v[i].y;
        c = v[i].c;

        if (get_father(x) != get_father(y))
        {
            ans += c;
            sol.push_back({x, y});
            unite(x, y);
        }
    }

    g << ans << '\n' << sol.size() << '\n';

    for (auto &it : sol)
        g << it.first << " " << it.second << '\n';
    return 0;
}