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

using namespace std;

const char iname[] = "apm.in";
const char oname[] = "apm.out";

vector <pair <int, pair <int, int> > > L;

vector <pair <int, int> > A;

vector <int> P;

void read_in(int &n) {
    ifstream in(iname);
    int cnt_edges, x, y, cost;
    in >> n >> cnt_edges;
    for (; cnt_edges --; ) {
        in >> x >> y >> cost;
        L.push_back( make_pair( cost, make_pair(x, y) ) );
    }
    in.close();
}

int find(const int n) {
    if (n != P[n])  P[n] = find(P[n]);
    return P[n];
}

int uniq(const int x, const int y) {
    (rand() & 1) ? P[x] = y : P[y] = x;
}

int main(void) {
    int n;
    read_in(n);
    sort(L.begin(), L.end());

    P.resize(n + 1);
    for (size_t i = 0; i < P.size(); ++ i)
        P[i] = i;
    int result = 0;
    for (size_t i = 0; i < L.size(); ++ i) {
        int x = L[i].second.first;
        int y = L[i].second.second;
        int cost = L[i].first;
        if (find(x) != find(y))
            uniq(find(x), find(y)), result += cost, A.push_back( make_pair(x, y) );
    }

    ofstream out(oname);
    out << result << "\n";
    out << A.size() << "\n";
    for (size_t i = 0; i < A.size(); ++ i)
        out << A[i].first << " " << A[i].second << "\n";
    out.close();

    return 0;
}