#include <bits/stdc++.h>
#define inf 2e8

using namespace std;

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

struct Muchie {
    int u, v, c;
};

vector < Muchie > muchii;
vector <int> tata;
vector <int> h;
int n, m, k, s;

bool compare(Muchie a, Muchie b) {
    return a.c < b.c;
}


int find_tata(int nod) {
    if (tata[nod] == 0)
        return nod;
    else return find_tata(tata[nod]);

}

void unite(int u, int v) {
    int t1 = find_tata(u);
    int t2 = find_tata(v);
    if (h[t1] > h[t2])
            tata[t2] = t1;
    else {
        tata[t1] = t2;
            if (h[t1] == h[t2])
                h[t2] ++;
        }
}

int main() {
    fin >> n >> m;
    muchii.resize(m + 1);
    tata.resize(n + 1, 0);
    h.resize(n + 1, 0);

    for (int i = 1; i <= m; i++) {
        int x, y, c;
        fin >> x >> y >> c;
        muchii.push_back({x, y , c});
    }
    sort(muchii.begin(), muchii.end(), compare);
    int cost = 0;
    vector <pair <int, int> > rez;
    for (auto x : muchii) {
        if (find_tata(x.u) != find_tata(x.v)) {
            unite(x.u, x.v);
            cost += x.c;
            rez.push_back({x.u, x.v});
            if (rez.size() == n - 1)
                break;
        }
    }
    fout << cost << "\n";
    fout << rez.size() << "\n";
    for (auto x : rez) {
        fout << x.first << " " << x.second << "\n";
    }

return 0;
}