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

using namespace std;

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

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

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

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

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

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;
        color[i] = i;
    }

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

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

    g << ans << '\n' << n - 1 << '\n';

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