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

using namespace std;

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

struct much{
    int inc;
    int sf;
    int cost;
};

int n, m, nms, csfm, cost;

int main(){
    fin >> n >> m;
    vector<much> muchii(m + 1);
    vector<much> arb(m + 1);
    vector<int> comp(n + 1);
    for (size_t i = 1; i <= n; i++)
        comp[i] = i;
    for (size_t i = 1; i <= m; i++)
        fin >> muchii[i].inc >> muchii[i].sf >> muchii[i].cost;
    sort(muchii.begin() + 1, muchii.begin() + m + 1, [](much a, much b){
        return a.cost < b.cost;
    });
    for (size_t i = 1; nms < n - 1; i++)
        if(comp[muchii[i].inc] != comp[muchii[i].sf]){
            nms++; 
            cost += muchii[i].cost;
            arb[nms] = muchii[i];
            csfm = comp[muchii[i].sf];
            for (size_t j = 1; j <= n; j++)
                if(comp[j] == csfm)
                    comp[j] = comp[muchii[i].inc];
        }
    fout << cost << '\n' << n - 1 << '\n';
    for (size_t i = 1; i <= nms; i++)
        fout << arb[i].inc << ' ' << arb[i].sf << '\n';
    return 0;
}