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

using namespace std;

ifstream fin ("amp.in");
ofstream fout ("amp.out");

vector <pair<int, pair <int,  int>>> muchii;
int n, m;
int tata[100001];
int rang[100001];
vector <pair <int, int >> muchii_apm;
int cost_total;

int findd(int nod) {
    int c_nod = nod;

    while (tata[nod] != nod)
        nod = tata[nod];

    while (tata[c_nod] != nod) {
        int save = tata[c_nod];
        tata[c_nod] = nod;
        c_nod = save;
    }

    return nod;
}

int verif(int x, int y) {

    if (findd(x) == findd(y))
        return 1;
    return 0;
}

void unionn(int x, int y) {
    int tatax = findd(x);
    int tatay = findd(y);

    if (rang[tatax] > rang[tatay]) {
        rang[tatax] += rang[tatay];
        tata[tatay] = tatax;
        muchii_apm.push_back({x, y});
    } else {
        rang[tatay] += rang[tatax];
        tata[tatax] = tatay;
        muchii_apm.push_back({x, y});
    }
}


void Kruskal (int s) {
    for (auto muchie : muchii) {

        //cout << muchie.second.first << " " << muchie.second.second  << endl;

        if (verif(muchie.second.first, muchie.second.second) == 0) {

            //cout << muchie.second.first << " " << muchie.second.second  << endl;
            unionn(muchie.second.first, muchie.second.second);
            cost_total += muchie.first;
        }
    }
}

int main() {
    fin >> n >> m;
    for (int i = 1; i <= m; i ++) {
        int a, b, c;
        fin >> a >> b >> c;

        muchii.push_back({c, {a, b}});
        muchii.push_back({c, {b, a}});
    }

    for (int i = 1; i <= n; i ++)
        tata[i] = i, rang[i] = 1;

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

    Kruskal(1);

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

    for (auto muchie : muchii_apm)
        fout << muchie.first << " " << muchie.second << endl;

    return 0;
}