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

using namespace std;

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

int N, M;
int sum;
int T[200005];
vector<pair<int, int> > sol;

struct muchie
{
    int nod1, nod2, cost;
};
muchie V[200005];

bool cmp(muchie A, muchie B)
{
    return A.cost < B.cost;
}

int query(int x)
{
    if (T[x] == x)
        return x;
    return T[x] = query(T[x]);
}

void update(int x, int y)
{
    if (x > y)
        swap(x, y);
    T[x] = y;
}

int main()
{
    fin >> N >> M;
    for (int i = 1; i <= M; ++i)
        fin >> V[i].nod1 >> V[i].nod2 >> V[i].cost;

    sort(V + 1, V + M + 1, cmp);

    for (int i = 1; i <= N; ++i)
        T[i] = i;

    for (int i = 1; i <= M; ++i)
    {
        int rad1 = query(V[i].nod1);
        int rad2 = query(V[i].nod2);

        if (rad1 != rad2)
        {
            sum += V[i].cost;
            sol.push_back(make_pair(V[i].nod1, V[i].nod2));
            update(rad1, rad2);
        }
    }

    fout << sum << '\n';
    fout << sol.size() << '\n';
    for (vector<pair<int, int> >::iterator it = sol.begin(); it != sol.end(); ++it)
        fout << it->first << ' ' << it->second << '\n';

    fin.close();
    fout.close();
    return 0;
}