#include <bits/stdc++.h>
#define NMAX 200000
using namespace std;

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

struct muchie {
    int nod1;
    int nod2;
    int cost;
};

inline bool comp(muchie a, muchie b) {
    return a.cost < b.cost;
}

int n, m;
vector<muchie> muchii;
vector<muchie> sol;

int tata[NMAX + 5];
int h[NMAX + 5];

void initializare(int x) {
    tata[x] = 0;
    h[x] = 0;
}

int reprezentant(int x) {
    if(tata[x] == 0)
        return x;
    tata[x] = reprezentant(tata[x]);
    return tata[x];
}

void reuneste(int x, int y) {
    int rx, ry;
    rx = reprezentant(x);
    ry = reprezentant(y);
    if(h[rx] > h[ry]) 
        tata[ry] = rx;
    else {
        tata[rx] = ry;
        if(h[rx] == h[ry]) 
            h[ry]++;
    }
}

void read() {
    muchie e;
    fin >> n >> m;
    for(int i = 1; i <= m; ++i) {
        fin >> e.nod1 >> e.nod2 >> e.cost;
        muchii.emplace_back(e);
    }
}

void kruskal() {
    // sortam muchiile
    sort(muchii.begin(), muchii.end(), comp);
    for(int i = 1; i <= n; ++i)
        initializare(i);
    int ct_muchii = 0;
    int cost_total = 0;
    for(auto m : muchii) {
        int nod1 = m.nod1;
        int nod2 = m.nod2;
        int c = m.cost;
        if(reprezentant(nod1) != reprezentant(nod2)) {
            ct_muchii++;
            cost_total += c;
            sol.emplace_back(m);
            reuneste(nod1, nod2);
            if(ct_muchii == n - 1)
                break;
        }
    }

    fout << cost_total << "\n";
    fout << sol.size() << "\n";
    for(auto m : sol)
        fout << m.nod1 << " " << m.nod2 << "\n";

}

int main() {

    read();
    kruskal();
    return 0;
}