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

using namespace std;

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

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

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

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

void unite(int a, int b)
{
    color[get_color(a)] = get_color(b);
}

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

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))
    {
        ans += v[i].cost;
        unite(v[i].x, v[i].y);
        sol.push_back({v[i].x, v[i].y});
    }

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

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