#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;
vector<int> tata, rang;

// Funcție find cu compresia căilor
int find(int nod) {
    if (tata[nod] != nod) {
        tata[nod] = find(tata[nod]);
    }
    return tata[nod];
}

// Funcție union
void union_set(int x, int y) {
    int radacina_x = find(x);
    int radacina_y = find(y);
    if (rang[radacina_x] < rang[radacina_y]) {
        tata[radacina_x] = radacina_y;
    } else if (rang[radacina_x] > rang[radacina_y]) {
        tata[radacina_y] = radacina_x;
    } else {
        tata[radacina_y] = radacina_x;
        rang[radacina_x]++;
    }
}

int main(){
    fin >> n >> m;
    vector<much> muchii(m + 1);
    vector<much> arb(m + 1);
    vector<int> comp(n + 1);
    tata.resize(n + 1);
    rang.resize(n + 1, 0);
    for (size_t i = 1; i <= n; i++)
        comp[i] = i, tata[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(find(muchii[i].inc) != find(muchii[i].sf)){
            nms++; 
            cost += muchii[i].cost;
            arb[nms] = muchii[i];
            union_set(muchii[i].inc, muchii[i].sf);
        }
    fout << cost << '\n' << n - 1 << '\n';
    for (size_t i = 1; i <= nms; i++)
        fout << arb[i].inc << ' ' << arb[i].sf << '\n';
    return 0;
}