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

#define NMAX 200002
using namespace std;

int main() {
    ifstream fin("apm.in");
    ofstream fout("apm.out");
    int N, M;
    int a, b, cost;
    fin >> N >> M;
    vector<pair<int, int> > apm;
    vector<pair<int, pair<int, int> > > muchii;
    for(int i = 0; i < M; i++) {
        fin >> a >> b >> cost;
        muchii.push_back(make_pair(cost, make_pair(a, b)));
    }
    vector<int> paduri(N + 1);
    for(int i = 1; i <= N; i++) {
        paduri[i] = i;
    }

    sort(muchii.begin(), muchii.end());

    int cost_total = 0;
    int index_muchie = 0;
    while(apm.size() != N - 1) {
        a = muchii[index_muchie].second.first;
        b = muchii[index_muchie].second.second;
        if(paduri[a] != paduri[b]) {
            cost_total += muchii[index_muchie].first;
            apm.push_back(muchii[index_muchie].second);
            int id = paduri[b];
            for(int i = 1; i <= N; i++) {
                if(paduri[i] == id) {
                    paduri[i] = paduri[a];
                }
            }
        }
        index_muchie++;
    }

    fout << cost_total << endl;
    fout << apm.size() << endl;

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

    return 0;
}