#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#define NMAX 200005
using namespace std;

struct muchie {
    int x, y;
    short cost;
};
bool compare(const muchie &a, const muchie &b) {    return a.cost < b.cost;     };

vector<int> c[NMAX];

int main() {
    freopen("apm.in", "r", stdin);
    freopen("apm.out", "w", stdout);
    int nrM = 0, N, M, costTotal = 0;
    scanf("%d%d", &N, &M);
    vector<muchie> V;
    vector<int> apartineComp;
    apartineComp.assign(N + 1, 0);
    vector<pair<int, int> > Sol;
    for(int i = 1; i <= N; i++) {
        c[i].push_back(i);
        apartineComp[i] = i;
    }
    while(M--) {
        muchie m;
        scanf("%d%d%hd", &m.x, &m.y, &m.cost);
        V.push_back(m);
    }

    sort(V.begin(), V.end(), compare);
    M = 0;
    while(nrM < V.size() && M < N - 1) {
        int x = V[nrM].x,     y = V[nrM].y,     cost = V[nrM].cost;
        if(apartineComp[x] != apartineComp[y]) {
            for(int i = c[apartineComp[y]].size() - 1; i >= 0 ; i--) {
                c[apartineComp[x]].push_back(c[apartineComp[y]][i]);
                if(y != c[apartineComp[y]][i])
                    apartineComp[c[apartineComp[y]][i]] = apartineComp[x];
            }
            if(c[apartineComp[y]].size() > N / 4)
                vector<int>().swap(c[apartineComp[y]]);
            apartineComp[y] = apartineComp[x];
            Sol.push_back(make_pair(x, y));
            costTotal += cost;
            M++;
        }
        nrM++;
    }
    cout << costTotal << '\n' << N - 1 << '\n';
    for(int i = 0; i < Sol.size(); i++)
        cout << Sol[i].first << ' ' << Sol[i].second << '\n';

}