#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;

struct Muchie {
    int x, y, cost;
};

int parent[200005];
int rank_arr[200005];


int Find(int x) {
    if (parent[x] != x) {
        parent[x] = Find(parent[x]);
    }
    return parent[x];
}


void Union(int x, int y) {
    int px = Find(x);
    int py = Find(y);

    if (px == py) return;

    if (rank_arr[px] > rank_arr[py]) {
        parent[py] = px;
    } else if (rank_arr[px] < rank_arr[py]) {
        parent[px] = py;
    } else {
        parent[px] = py;
        rank_arr[py]++;
    }
}

bool cmp(const Muchie &a, const Muchie &b) {
    return a.cost < b.cost;
}

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

    int N, M;
    fin >> N >> M;

    vector<Muchie> E(M);

    for (int i = 0; i < M; i++) {
        fin >> E[i].x >> E[i].y >> E[i].cost;
    }


    for (int i = 1; i <= N; i++) {
        parent[i] = i;
        rank_arr[i] = 0;
    }


    sort(E.begin(), E.end(), cmp);


    vector<pair<int, int>> M_sol;
    long long sol = 0;

    for (int i = 0; i < M && M_sol.size() < N - 1; i++) {
        if (Find(E[i].x) != Find(E[i].y)) {
            sol += E[i].cost;
            M_sol.push_back({E[i].x, E[i].y});
            Union(E[i].x, E[i].y);
        }
    }

    fout << sol << "\n";
    fout << M_sol.size() << "\n";
    for (auto &m : M_sol) {
        fout << m.first << " " << m.second << "\n";
    }

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