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

using namespace std;

#define NMAX 200010
#define INF (1 << 30)
struct muchie {
        int u, v, w;
    };
bool cmp(muchie a, muchie b) {
        return a.w < b.w;
}
class Task {
public:
    void solve() {
        read_input();
        get_result();
        print_output();
    }

private:

    int n, m, apm;

    vector<int> p;
    vector<pair<int, int> >sol;
    vector<muchie> muc;

    void read_input() {
        cin >> n >> m;

        for(int i = 1; i <= m; ++i) {
            int x, y, c;
            cin >> x >> y >> c;
            muc.push_back({x, y, c});
        }
    }

    void get_result() {
        Kruskal();
    }

    int find_tata(int nod) {
        if(p[nod] == nod) {
            return nod;
        }
        int ans = find_tata(p[nod]);
        p[nod] = ans;
        return ans;
    }
    void Kruskal() {
        p = vector<int>(n + 1);
        for(int i = 1; i <= n; ++i) {
            p[i] = i;
        }
        apm = 0;
        sort(muc.begin(), muc.end(), cmp);
        for(int i = 0; i < muc.size(); ++i) {
            int tu = find_tata(muc[i].u);
            int tv = find_tata(muc[i].v);
            if(tu != tv) {
                p[tu] = tv;
                sol.push_back({muc[i].u, muc[i].v});
                apm += muc[i].w;
            }
        }
    }

    void print_output() {
        cout << apm << '\n';
        cout << n - 1 << '\n';
        for (int i = 0; i < n - 1; ++i) {
            cout << sol[i].first << ' ' << sol[i].second << '\n';
        }
    }
};

int main() {
    // din cauza ca fac redirectari, salvez starea lui cin si cout
    auto cin_buff = cin.rdbuf();
    auto cout_buff = cout.rdbuf();

    // las liniile urmatoare daca citesc din fisier
    ifstream fin("apm.in");
    cin.rdbuf(fin.rdbuf()); // save and redirect

    // las liniile urmatoare daca afisez in fisier
    ofstream fout("apm.out");
    cout.rdbuf(fout.rdbuf()); // save and redirect

    // aici este rezolvarea propriu-zisa
    Task *task = new Task();
    task->solve();
    delete task;

    // restore pentru cin si cout
    cin.rdbuf(cin_buff);
    cout.rdbuf(cout_buff);

    // obs. nu e nevoie sa inchid fisierele
    // cand se apeleaza destructorii pentru fin si fout se vor inchide

    return 0;
}