#include <bits/stdc++.h>

using namespace std;

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

using ppi = pair<pair<int, int>, int>;
using pi = pair<int, int>;

struct comp
{
    bool operator()(const ppi a, const ppi b)
    {
        return a.second > b.second;
    }
};

using prQ = priority_queue<ppi, vector<ppi>, comp>;

void test(prQ pq)
{
    while (!pq.empty())
    {
        fout << pq.top().first.first << " " << pq.top().first.second << " " << pq.top().second << '\n';
        pq.pop();
    }
}

int n, m, x, y, k, cost, nrm;
int g[200001];

int grupa(int i)
{
    if (g[i] == i) return i;
    else {
        g[i] = grupa(g[i]);
        return g[i];
    }
}

void reuniune(int a, int b)
{
    g[grupa(a)] = grupa(b);
}

queue<pi> apm;

void creare(prQ pq)
{
    for (int i = 1; i <= n; i++)
        g[i] = i;
    while (!pq.empty())
    {
        int vp = pq.top().first.first, vu = pq.top().first.second, c = pq.top().second;
        if (grupa(vp) != grupa(vu))
        {
            apm.push(make_pair(vp, vu));
            reuniune(vp, vu);
            cost += c;
            nrm++;
        }
        pq.pop();
    }
}

void afis(queue<pi> q)
{
    while (!q.empty())
    {
        fout << q.front().first << " " << q.front().second << '\n';
        q.pop();
    }
}

int main()
{
    prQ pq;
    f >> n >> m;
    for (int i = 1; i <= m; i++)
    {
        f >> x >> y >> k;
        pq.push(make_pair(make_pair(x, y), k));
    }
    //test(pq);
    creare(pq);
    fout << cost << '\n';
    fout << nrm << '\n';
    afis(apm);
}