#include <bits/stdc++.h>

#define NMax 100001

using namespace std;

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


class graf
{
    int nrNoduri, nrMuchii;
    bool orientat;
    pair< int, pair<int, int> > v[NMax]; // structura de date pt APM


public:
    graf(int n, int m, bool o); // constructor
    void Citire_Neorientat_Costuri();

    //APM
    void Kruskal();
};

graf :: graf(int n, int m, bool o)
{
    nrNoduri = n;
    nrMuchii = m;
    orientat = o;
}

void graf :: Citire_Neorientat_Costuri()
{
    for(int i = 1; i <= nrMuchii; ++i)
    {
        fin >> v[i].second.first >> v[i].second.second; // muchia (x,y)
        fin >> v[i].first;                              // cu costul c
    }
}



int C[200001];       // C[x] = numarul componentei conexe din care face parte nodul x
int cost = 0, ct_muchii_adaugate = 0;
int Sol[200001];


void graf :: Kruskal()
{
    sort(v + 1, v + nrMuchii + 1); // sortam crescator muchiile in functie de cost


    for(int i = 1; i <= nrNoduri; ++i) C[i] = i;        // initial se pleaca cu n arbori formati dintr-un singur nod

    for(int i = 1; i <= nrMuchii && ct_muchii_adaugate < nrNoduri - 1; ++i)
    {
        // verificam daca muchia i poate fi adaugata
        // cele doua extremitati trebuie sa faca parte din compomnente conexe diferite
        if(C[v[i].second.first] != C[v[i].second.second])
        {
            cost += v[i].first;      // marim costul arborelui

            ct_muchii_adaugate++;    // adaugam muchia de ordin i la arbore
            Sol[ct_muchii_adaugate] = i;

            // unificare
            int cx = C[v[i].second.first];
            int cy = C[v[i].second.second];
            for(int j = 1; j <= nrNoduri; ++j)
                if(C[j] == cx)
                    C[j] = cy;
        }
    }

    // afisare cost, nr muchii si muchii
    fout << cost << "\n" << ct_muchii_adaugate << "\n";
    for(int i = 1; i <= ct_muchii_adaugate; ++i)
        fout<<v[ Sol[i] ].second.first << " " << v[ Sol[i] ].second.second << "\n";

}



int N, M;

int main()
{
    fin >> N >> M;
    graf G(N, M, 0);
    G.Citire_Neorientat_Costuri();
    G.Kruskal();

    return 0;
}