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

#define MAXN 200010

using namespace std;

struct edge {
    int x, y, c;
    edge(int x = 0, int y = 0, int c = 0)
        : x(x), y(y), c(c) {}
};

struct cmp {
    int operator()(const edge& e1, const edge& e2) {
        return e1.c < e2.c;
    }
};

int N, M, TT[MAXN], costAPM;
vector<edge> E;
vector<int> sol;


int find(int x) {
    if (TT[x] == x)
        return x;
    else
        return TT[x] = find(TT[x]);
}

void unite(int x, int y) {
    TT[find(y)] = find(x);
}

void Kruskal() {
    sort(E.begin(), E.end(), cmp());

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

    for (int i = 0; i < M && sol.size() < N - 1; ++i) {
        if (find(E[i].x) != find(E[i].y)) {
            costAPM += E[i].c;
            unite(E[i].x, E[i].y);
            sol.push_back(i);
        }
    }
}

int main()
{
    iostream::sync_with_stdio(false);
    freopen("apm.in", "r", stdin);
    freopen("apm.out", "w", stdout);

    cin >> N >> M;
    int x, y, c;
    for (int i = 1; i <= M; ++i) {
        cin >> x >> y >> c;
        E.push_back(edge(x, y, c));
    }

    Kruskal();

    cout << costAPM << "\n" << sol.size() << "\n";
    for (int x : sol) {
        cout << E[x].x << " " << E[x].y << "\n";
    }

    return 0;
}