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

#define MaxN 200005

using namespace std;

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

int TT[MaxN], RG[MaxN];

int myfind(int x) {
    int parent;

    for (parent = x; parent != TT[parent]; parent = TT[parent]);

    while (x != parent) {
        int temp = TT[x];
        TT[x] = parent;
        x = temp;
    }

    return parent;
}

void myunion(int x, int y) {
    if (RG[x] < RG[y]) {
        TT[x] = y;
        RG[y] += RG[x];
    } else {
        TT[y] = x;
        RG[x] += RG[y];
    }
}

int main()
{
    int N, M;
    fin >> N >> M;

    for (int i = 1; i <= N; ++i)
        TT[i] = i, RG[i] = 1;

    vector<pair<int, pair<int, int> > > v;
    for (int i = 0; i < M; ++i) {
        int x, y, c;
        fin >> x >> y >> c;
        v.push_back(make_pair(c, make_pair(x, y)));
    }

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

    vector<pair<int, int> > result;

    int minCost = 0;
    int neededEdges = N - 1, iter = 0;
    while (neededEdges > 0) {
        int cost = v[iter].first;
        int x = v[iter].second.first;
        int y = v[iter].second.second;

        ++iter;

        int parentX = myfind(x);
        int parentY = myfind(y);
        if (parentX != parentY) {
            myunion(parentX, parentY);

            minCost += cost;
            result.push_back(make_pair(x, y));

            --neededEdges;
        }
    }

    fout << minCost << '\n' << result.size() << '\n';
    for (int i = 0; i < result.size(); ++i) {
        fout << result[i].first << ' ' << result[i].second << '\n';
    }

    return 0;
}