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

#define MAXN 200005

using namespace std;

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

struct str{
    int x, y, s;

    bool operator < (const str& other) const {
        return s < other.s;
    }
};

str v[MAXN];
int dad[MAXN];

vector <int> sol;

inline void Read(int &N, int &M, str v[]) {
    fin >> N >> M;

    for (int i = 1; i <= M; i++) {
        fin >> v[i].x >> v[i].y >> v[i].s;
    }
}

int parinte(int node) {
    if (node != dad[node])
        return dad[node] = parinte(dad[node]);
    return dad[node];
}

inline void Initializare(int N, int dad[]) {
    for (int i = 1; i <= N; i++)
        dad[i] = i;
}

inline void APM(int N, int M, int &cost, int dad[], str v[]) {
    int p1, p2; cost = 0;

    sort(v + 1, v + M + 1);

    for (int i = 1; i <= M; i++) {
        p1 = parinte(v[i].x);
        p2 = parinte(v[i].y);

        if (p1 != p2) {
            dad[p1] = p2;
            cost += v[i].s;
            sol.push_back(i);
        }
    }
}

inline void Write(int cost) {
    fout << cost << "\n";
    fout << sol.size() << "\n";

    for (auto i : sol)
        fout << v[i].x << " " << v[i].y << "\n";
}

int main() {
    int N, M, cost;

    Read(N, M, v);
    Initializare(N, dad);
    APM(N, M, cost, dad, v);
    Write(cost);

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