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

using namespace std;

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

int i, n, m, color[NMAX], sum = 0;
vector < pair < int, int > > ans;

struct muchie
{
    int x, y, cost;
};
muchie v[NMAX];

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

int get_color(int x)
{
    if (color[x] != x)
        color[x] = get_color(color[x]);
    return color[x];
}

void unite(int x, int y)
{
    color[get_color(x)] = get_color(y);
}

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

    for (i = 1; i <= m; ++ i)
        f >> v[i].x >> v[i].y >> v[i].cost;

    for (i = 1; i <= n; ++ i)
        color[i] = i;

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

    for (i = 1; i <= m; ++ i)
    {
        if (get_color(v[i].x) != get_color(v[i].y))
        {
            sum += v[i].cost;
            ans.push_back({v[i].x, v[i].y});
            unite(v[i].x, v[i].y);
        }
    }

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

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