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

using namespace std;

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

struct muchie
{
    int nod1, nod2, cost;
};

vector<muchie> v;
vector <pair<int, int>> sol;
int N, M, n1, n2, c, tata[200005], total;

bool cmp (muchie m1, muchie m2)
{
    if (m1.cost > m2.cost)
        return false;
    return true;
}

int sef(int nod)
{
    if (tata[nod] == nod)
        return nod;
    else
        return tata[nod] = sef(tata[nod]);
}

void unire(int nod1, int nod2)
{
    int sef1 = sef(nod1);
    int sef2 = sef(nod2);
    tata[sef1] = sef2;
}

int main()
{
    f >> N >> M;
    for (int i = 1; i<=M; ++i)
    {
        f >> n1 >> n2 >> c;
        v.push_back({n1, n2, c});
    }
    sort(v.begin(), v.end(), cmp);
    /*for (int i = 0; i<v.size(); ++i)
        cout << v[i].nod1 << ' ' << v[i].nod2 << ' ' << v[i].cost << '\n';*/
    for (int i = 1; i<=N; ++i)
        tata[i] = i;
    int i = 0;
    while (sol.size() < N-1)
    {
        n1 = v[i].nod1;
        n2 = v[i].nod2;
        c = v[i].cost;
        if (sef(n1) != sef(n2))
        {
            unire(n1, n2);
            sol.push_back(make_pair(n1, n2));
            total+=c;
        }
        ++i;
    }
    g << total << '\n';
    g << sol.size() << '\n';
    for (int i = 0; i<sol.size(); ++i)
        g << sol[i].first << ' ' << sol[i].second << '\n';
    return 0;
}