#include <bits/stdc++.h>

using namespace std;

struct muchie{
    int i, j, cost;
};

class multimi_disjuncte{
public:
    vector<int>root;
    multimi_disjuncte(const int n = 0) {
        root = vector<int>(n + 1);
        iota(begin(root), end(root), 0);
    }
    int tata(int x) {
        return x == root[x] ? x : root[x] = tata(root[x]);}
    void unite(int x, int y) {
        root[tata(x)] = tata(y);
    }
};

int main() {
    ifstream cin("apm.in");
    ofstream cout("apm.out");

    int n, m;
    cin >> n >> m;

    vector <muchie> muchii(m);
    for(int i = 0; i < m ; ++i) {
        cin >> muchii[i].i >> muchii[i].j >> muchii[i].cost;
        muchii[i].i--, muchii[i].j--;
    }

    sort(begin(muchii), end(muchii), [] (const muchie &lhs, const muchie &rhs) { return lhs.cost < rhs.cost;});
    multimi_disjuncte padure(n);
    int ans = 0;
    vector < pair <int, int > > muc_apm;
    for(auto edges : muchii) {
        if(padure.tata(edges.i) != padure.tata(edges.j))
          ans += edges.cost, muc_apm.emplace_back(edges.i, edges.j), padure.unite(edges.i, edges.j);
    }

    cout << ans << '\n' << n - 1 << '\n';
    for(auto edges : muc_apm)
        cout << edges.first+1 << ' ' << edges.second+1 << '\n';
    return 0;
}