#include <bits/stdc++.h>
//Determinare apcm cu algoritmul lui Kruskal
//Complex: O(n^2 + mlogn)
/* Determinare APCM folosind colorarea componentelor (se asociaza fiecarei submultimi o culoare)
    r[u]= culoarea compnentei din care varful u face parte
    graf neorientat
    lucrez pe lista de muchii (x, y, cost)

Pe infoarena va da limita de timp depasita!!!
*/
using namespace std;
ifstream fin("apm.in");  // Deschide fișierul pentru citire
ofstream fout("apm.out");  // Deschide fișierul pentru scriere

struct muchie { //structura care mem o muchie: nod intrare, nod iserie, costul muchiei
    int nod_intrare, nod_iesire, cost;
};

vector<muchie> muchii; //lista de muchii ale grafului
vector<int> tata, h; //lista culorilor pentru fiecare nod din graf

int N, M;
int cost_apcm = 0;
vector<muchie> apcm;

void Initializare(int u) { //initializam ca culoarea unui nod sa fie fix el insusi(culoarea lui 1 e 1)
    tata[u] = 0;
    h[u] = 0;
}

int Reprez(int u) { //find( varf u ) = culoarea lui u
    while(tata[u] !=0)
        u = tata[u];
    return u;
}

void Reuneste(int u, int v) { //construirea muchiei pt apcm cu 2 vf u si v
    int ru = Reprez(u);
    int rv = Reprez(v);
    if(h[ru] > h[rv])
        tata[rv] = ru;
    else
    {
        tata[ru] = rv;
        if(h[ru] == h[rv])
            h[rv]+=1;
    }
}

bool Compara(muchie a, muchie b) {
    return a.cost < b.cost; //compararea costurilor a 2 muchii
}
void Kruskal()
{
  //De aici incepe Kruskal
    for (int i = 1; i <= N; i++) {
        Initializare(i);
    }


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



    for (int i = 0; i < M; i++) {
        int x = muchii[i].nod_intrare;
        int y = muchii[i].nod_iesire;
        int cost = muchii[i].cost;

        if (Reprez(x) != Reprez(y)) {
            Reuneste(x, y);
            cost_apcm += cost;
            apcm.push_back(muchii[i]);
        }
    }
}

int main() {
    fin >> N >> M; //citim nr de noduri si de muchii

    muchii.resize(M); //redimensionam lista de muchii = nr muchii
    tata.resize(N + 1);
    h.resize(N + 1);

     for (int i = 0; i < M; i++) {
        int x, y, C;
        fin >> x >> y >> C;
        muchie m;
        m.nod_intrare = x;
        m.nod_iesire = y;
        m.cost = C;
        muchii[i] = m;
    }
    Kruskal();

    fout << cost_apcm << "\n"; //costul apcm
    fout << apcm.size() << "\n"; //nr muchii apcm
    for (auto m : apcm) { //muchiile apcm
        fout << m.nod_iesire << " " << m.nod_intrare << "\n";
    }

    return 0;
}