#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>
using namespace std;

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

struct muchie
{
    int i, j, cost;
};

int n, m;
int t[200001];
muchie x[400001];
vector<pair<int,int>> sol;

int Find(int nod)
{
    if (t[nod] == nod) return nod;
    return t[nod] = Find(t[nod]);
}

void Union(int a, int b)
{
    t[Find(b)] = Find(a);
}

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

    for (int i = 1; i <= m; i++)
        in >> x[i].i >> x[i].j >> x[i].cost;

    sort(x + 1, x + m + 1, [](const muchie &a, const muchie &b)
    {
        return a.cost < b.cost;
    });

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

    int S = 0;

    for (int i = 1; i <= m; i++)
    {
        int a = Find(x[i].i);
        int b = Find(x[i].j);
        if (a != b)
        {
            Union(a, b);
            S += x[i].cost;
            sol.push_back({x[i].i, x[i].j});
        }
    }

    out << S << "\n";
    out << sol.size() << "\n";
    for (auto &e : sol)
        out << e.first << " " << e.second << "\n";

    return 0;
}