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

using namespace std;

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

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

struct ceva
{
    int x, y, cost;
    bool operator < (const ceva &a)const
    {
        return cost < a.cost;
    }
};

vector <pair <int, int> > sol;

vector <ceva> l;

int n, m, x, y, cost, ans;

struct dsu{
    int rad (int node)
    {
        if (node == tata[node])return node;
        return tata[node] = rad (tata[node]);
    }
    void unite (ceva node)
    {
        int rx = rad(node.x);
        int ry = rad (node.y);
        if (rx != ry)
        {
            sol.push_back({node.x, node.y});
            ans += node.cost;
            if (rang[rx] > rang[ry])
                swap(rx, ry);
            if (rang[rx] == rang[ry])
                ++rang[ry];
            tata[rx] = ry;
        }
    }
}v;

int main()
{
    cin >> n >> m;
    for (int i = 1; i <= m; ++i)
    {
        cin >> x >> y >> cost;
        l.push_back({x, y, cost});
    }
    for (int i = 1; i <= n; ++i)
        tata[i] = i, rang[i] = 1;
    sort (l.begin(), l.end());
    for (auto it : l)
        v.unite (it);
    cout << ans << '\n' << sol.size() << '\n';
    for (auto it : sol)
        cout << it.first << ' ' << it.second << '\n';
    return 0;
}