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

using namespace std;
ifstream in("apm.in");
ofstream out("apm.out");

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

bool operator<(const muchie &a, const muchie &b) {
    if (a.cost == b.cost)
        return a.x < b.x;
    return a.cost < b.cost;
}

vector<int> Tata;
vector<int> Depth;

int FindRepr(int i) {
    if (Tata[i] == -1)
        return i;
    Tata[i] = FindRepr(Tata[i]);
    return FindRepr(Tata[i]);
}
bool Union(muchie A) {
    int reprX = FindRepr(A.x);
    int reprY = FindRepr(A.y);

    if (reprX == reprY)
        return false;

    if (Depth[reprX] < Depth[reprY]) {
        Tata[reprX] = reprY;
    }
    else if (Depth[reprX] > Depth[reprY]) {
        Tata[reprY] = reprX;
    }
    else {
        Tata[reprX] = reprY;
        Depth[reprY] += 1;
    }
    return true;
}



int main() {
    int n, m;
    in >> n >> m;

    vector<muchie> v(m);
    Tata.resize(n, -1);
    Depth.resize(n, 0);

    for (int i = 0; i < m; i++) {
        in >> v[i].x >> v[i].y >> v[i].cost;
        v[i].x--; v[i].y--;
    }

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

    vector<muchie> ans;
    int total_cost = 0;

    for (int i = 0; i < m; i++) {
        if (ans.size() == n - 1)
            break;
        if (Union(v[i])) {
            ans.push_back(v[i]);
            total_cost += v[i].cost;
        }
    }

    out << total_cost << "\n";
    out << ans.size() << "\n";
    for (muchie& X : ans) {
        out << ++X.x << " " << ++X.y << "\n";
    }

    return 0;
}