/*
    Algoritmul lui Kruskal - APM - 100p
    Note:
        -Kruskal e mai rapid decat Prim in majoritatea cazurilor
        -Pe grafuri dense, Prim e mai optim
        -Kruskal foloseste paduri disjuncte
        -Kruskal ofera posibilitatea de a retine DOAR muchiile,
         ceea ce il face mai optim dpdv al memoriei
        -"Kruskal deobicei, Prim pe grafuri dense"
*/
#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;

#define PII pair<int,int>
#define Edge pair<int,PII>
#define cost first
#define x second.first
#define y second.second

ifstream is ("apm.in");
ofstream os ("apm.out");

int N, M;                   //numarul de noduri, numarul de muchii
int T[200002];              //T[i] = tatal lui i
int R[200002];              //R[i] = adancimea maxima la care se poate ajunge pornind din i
int APMcost;                //costul APM-ului

vector <Edge> E;            //Muchiile {*cost*, {*nod*, *nod*}}
vector <PII> APM;           //APM-ul {*nod*, *nod*}

void Kruskal();
int Root(int k);            //returneaza radacina nodului k
void Unite(int a, int b);   //uneste radacinile

int main()
{
    is >> N >> M;
    for (int i = 1, a, b, c; i <= M; ++i)
    {
        is >> a >> b >> c;                  //
        E.push_back({c, {a, b}});           //citire
    }
    Kruskal();                              ///REZOLVARE
    is.close();
    is.close();
}

void Kruskal()
{
    for (int i = 1; i <= N; ++i)
        T[i] = i, R[i] = 1;             //initializam padurile
    sort(E.begin(), E.end());           //sortam muchiile dupa cost
    int Rx, Ry;         //radacini
    for (const auto& m : E)
    {
        Rx = Root(m.x);
        Ry = Root(m.y);
        if (Rx == Ry);          //daca radacinile sunt aceleasi, inseamna ca daca
                                        //am adauga muchia la APM am avea un ciclu,
                                        //deci nu ar mai fi arbore
        else                    //daca radacinile difera
        {
            Unite(Rx, Ry);              //unim cele doua radacini in mod OPTIM
            APMcost += m.cost;          //adaugam costul muchiei la APM
            APM.push_back({m.x, m.y});  //introducem muchia in APM
        }
        if (APM.size() >= N-1)          //stim ca APM-ul va avea fix N-1 muchii
            break;                      //deci daca avem deja N-1 muchii, iesim din for
    }
    os << APMcost << '\n' << APM.size() << '\n';           //
    for (const auto& m : APM)                       // Afisare
        os << m.first << ' ' << m.second << '\n';   //
};

int Root(int k)                 //cautam radacina in mod OPTIM
{
    int r = k;
    for (; T[r] != r; r = T[r]);
    for (int s; T[k] != k; s = T[k], T[k] = r, k = s);
    return r;
};

void Unite(int a, int b)        //unim cele doua radacini in mod OPTIM
{
    if (R[a] > R[b])
        T[b] = a;
    else
    {
        T[a] = b;
        if (R[a] == R[b])
            R[b]++;
    }
};