#include <bits/stdc++.h>
#define NMax 100001

using namespace std;

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

int nrNoduri, nrMuchii;
pair< int, pair<int, int> > v[4*NMax]; // structura de date pt APM

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


void Kruskal()
{

    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
    }


    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 main()
{
    fin >> nrNoduri >> nrMuchii;
    Kruskal();

    return 0;
}