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

using namespace std;

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

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

vector <tuple <int, int, int> > v;
vector <pair <int, int > > p;

int n, m, nod1, nod2, cost;

int rad (int nod)
{
    if (!tata[nod])
        return nod;
    tata[nod] = rad(tata[nod]);
    return tata[nod];
}

int main()
{
    for (cin >> n >> m; m; --m)
    {
        cin >> nod1 >> nod2 >> cost;
        v.push_back(make_tuple(nod1, nod2, cost));
    }
    sort (v.begin(), v.end(),
          [] (const tuple <int, int,int> &a, const tuple <int, int, int> &b)
    {
        return (get <2>(a) < get <2>(b));
    });
    int costmin = 0;
    for (auto it : v)
    {
        int x, y, c;
        tie (x, y, c) = it;
        int rx = rad(x);
        int ry = rad(y);
        if (rx != ry)
        {
            tata[rx] = ry;
            p.push_back({x, y});
            costmin += c;
        }
    }
    cout << costmin << '\n' << p.size() << '\n';
    for (auto it : p)
        cout << it.first << ' ' << it.second << '\n';
    return 0;
}