///prim vs kruskal

#include <fstream>
#include <vector>
#include <algorithm>

using namespace std;

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

using pa = pair <int, int>;

const int N = 2e5;
int tata[N + 1], rang[N + 1];

int n, m, sum;

vector <pa> sol;

struct muchie
{
    int x, y, cost;
    friend istream &operator >> (istream &is, muchie &a)
    {
        is >> a.x >> a.y >> a.cost;
        return is;
    }
    bool operator < (const muchie &a)const
    {
        return cost < a.cost;
    }
};

namespace DSU
{
int rad (int node)
{
    if (node == tata[node])return node;
    return tata[node] = rad(tata[node]);
}
void unite (muchie a)
{
    int rx = rad (a.x);
    int ry = rad (a.y);
    if (rx != ry)
    {
        sum += a.cost;
        sol.push_back({a.x, a.y});
        if (rang[rx] < rang[ry])
            tata[rx] = ry;
        else if (rang[ry] < rang[rx])
            tata[ry] = rx;
        else
            tata[rx] = ry, ++rang[ry];

    }
}
}

vector <muchie> edge;

int main()
{
    cin >> n >> m;
    edge.resize(m);
    for (int i = 0; i < m; ++i)
        cin >> edge[i];
    for (int i = 1; i <= n; ++i)
        tata[i] = i;
    sort (edge.begin(), edge.end());
    for (auto it : edge)
        DSU::unite(it);
    cout << sum << '\n';
    cout << sol.size() << '\n';
    for (auto it : sol)
        cout << it.first << ' ' << it.second << '\n';
    return 0;
}