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

using namespace std;

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

int r[200005], n, mu;

vector <pair <int, pair<int, int> > > m;
vector <pair <int, int> > sol;

int _find(int x);
void _union(int x, int y);

int main()
{
    cin >> n >> mu;

    for(int i = 1; i <= mu; i++)
    {
        int x, y, c;

        cin >> x >> y >> c;

        m.push_back(make_pair(c, make_pair(x, y)));
    }

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

    sort(m.begin(), m.end());

    int cost = 0;

    for(int i = 0; i < m.size(); i++)
    {
        int x = m[i].second.first;
        int y = m[i].second.second;
        int rx = _find(x);
        int ry = _find(y);

        if(rx == ry)
            continue;

        cost += m[i].first;
        sol.push_back(make_pair(x, y));
        _union(rx, ry);
    }

    cout << cost << '\n' << sol.size() << '\n';

    for(int i = 0; i < sol.size(); i++)
        cout << sol[i].first << " " << sol[i].second << '\n';

    return 0;
}

int _find(int x)
{
    if(x == r[x])
        return x;

    r[x] = _find(r[x]);

    return r[x];
}

void _union(int x, int y)
{
    int rx = _find(x);
    int ry = _find(y);

    r[ry] = x;
}