#include <iostream>
#include <vector>
#include <queue>
#include <fstream>
using namespace std;
ifstream fin("apm.in");
ofstream fout("apm.out");

priority_queue<pair<int, pair<int, int> > >muchii;
vector<pair<int, int> >graf_final;
int tata[2000003];
int grad[2000000];

int find_father(int node) {
    if (tata[node] == node)
        return node;
    tata[node] = find_father(tata[node]);
    return tata[node];
}

int main() {
    int N, M, X, Y, C, i;
    fin >> N>>M;
    for (i = 1; i <= N; i++) {
        grad[i] = 1;
        tata[i] = i;
    }
    for (i = 0; i < M; i++) {
        fin >> X >> Y>>C;
        muchii.push(make_pair((-1 * C), make_pair(X, Y)));
    }
    int cost = 0;
    while (!muchii.empty()) {
        pair<int, int>muchie;
        pair<int, pair<int, int> >p = muchii.top();
        muchii.pop();
        muchie = p.second;
        int t_first, t_second;
        t_first = find_father(muchie.first);
        t_second = find_father(muchie.second);
        if (t_first != t_second) {
            if (grad[t_first] < grad[t_second]) {
                tata[t_first] = t_second;
                grad[t_second] += grad[t_first];
                graf_final.push_back(make_pair(muchie.first, muchie.second));
                cost += (-1) * p.first;
            } else {
                tata[t_second] = t_first;
                grad[t_first] += grad[t_second];
                graf_final.push_back(make_pair(muchie.first, muchie.second));
                cost += (-1) * p.first;
            }
        }

    }
    fout << cost << endl;
    fout << graf_final.size() << endl;
    for (int i = 0; i < graf_final.size(); i++)
        fout << graf_final[i].first << " " << graf_final[i].second << endl;
    return 0;
}