#include <bits/stdc++.h>

using namespace std;

int Find(int nod, const vector<int> & tata) {
    while (tata[nod]) {
        nod = tata[nod];
    }
    return nod;
}

void Union(const int u,const int v, vector<int> & tata, vector<int> & h) {
    const int ru = Find(u, tata);
    const int rv = Find(v, tata);

    if (ru != rv) {
        if (h[ru] > h[rv]) {
            tata[rv] = ru;
        } else {
            tata[ru] = rv;
            if (h[ru] == h[rv]) {
                h[ru]+=1;
            }
        }
    }
}

bool cmpThird(tuple<int, int, int> & x, tuple<int, int, int> & y) {
    return get<2>(x) < get<2>(y);
}

void Kruskal() {
    ifstream cin("apm.in");
    ofstream cout("apm.out");

    int n, m;
    cin>> n >>m;
    vector<tuple<int, int, int>> list_muchi;
    vector<pair<int, int>> lista_muchii_arbore;
    vector<int> tata(n+1, 0), h(n+1, 0);

    for (int i=1; i<=m; i++) {
        int u, v, w;
        cin>> u >> v>> w ;
        list_muchi.emplace_back(u, v, w);
    }
    sort(list_muchi.begin(), list_muchi.end(), cmpThird);

    int nr_muchii = 0, cost = 0;
    for (auto muchie : list_muchi) {
        int u = get<0>(muchie), v = get<1>(muchie), w = get<2>(muchie);
        if (Find(u, tata) != Find(v, tata)) {
            Union(u, v, tata, h);
            nr_muchii++;
            cost+=w;
            lista_muchii_arbore.emplace_back(v, u);
            if (nr_muchii == n-1)
                break;
        }
    }

    cout <<cost <<'\n' <<nr_muchii<<'\n';
    for (auto muchie :lista_muchii_arbore) {
        cout<< muchie.first <<' '<< muchie.second<<'\n';
    }
}
int main() {
    Kruskal();
}