#include <iostream>
#include <algorithm>
#include <fstream>
#include <set>
using namespace std;

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

struct arch {
    int start, end, cost;
};

const int MAX_PEAKS = 200005;
const int MAX_ARCHES = 400005;

int noPeaks, noArches, representants[MAX_PEAKS];
set<pair<int, pair<int, int>>> arches;

int main() {
    fin >> noPeaks >> noArches;
    for (int i = 1 ; i <= noArches ; ++i) {
        int start, end, cost;
        fin >> start >> end >> cost;
        pair<int, int> arch = make_pair(start, end);
        arches.insert(make_pair(cost, arch));
    }
    int minSum = 0, noUnitedTreeArches = 0;
    arch unitedTree[MAX_ARCHES];
    int i = 0;
    for (pair<int, pair<int, int>> e : arches) { // iterates through all the "sorted by cost" arches
        ++i;
        int start = e.second.first;
        int end = e.second.second;
        int cost = e.first;
        if (representants[start] != representants[end] || representants[start] == 0 || representants[end] == 0) { // if it unites 2 different trees
            if (representants[start] == 0) {
                representants[start] = i;
            }
            if (representants[end] == 0) {
                representants[end] = i;
            }
            unitedTree[++noUnitedTreeArches].start = start;
            unitedTree[noUnitedTreeArches].end = end;
            minSum += cost;
            int firstRepresentant = representants[start], secondRepresentant = representants[end]; // we unite the 2 separate trees
            for (int j = 1; j <= noPeaks; ++j) { // we mark the elements from the other tree with the first representant
                if (representants[j] == secondRepresentant) {
                    representants[j] = firstRepresentant;
                }
            }
        }
    }
    fout << minSum << "\n" << noUnitedTreeArches << "\n";
    for (int i = 1; i <= noUnitedTreeArches; ++i) {
        fout << unitedTree[i].start << " " << unitedTree[i].end << "\n";
    }
    return 0;
}


/*
 ideea algoritmului lui Krustal:
 
 Trebuie sa formam un arbore de cost minim care se formeaza din toate varfurile din graful initial, fiecare muchie avand un cost anume.
 Vom sorta muchiile dupa costul lor. Pornim de la faptul ca fiecare punct formeaza singur cate un arbore.
 Fiecare arbore va avea un "reprezentant", asta insemnand ca fiecare valoare dintr-un anumit arbore va fi egala cu valoarea reprezentatului. La inceput, reprezentantii vor avea valori de la 1....n (numar de varfuri)
 In continuare, vrem sa unim acesti reprezentanti. Iteram toate muchiile sortate, iar daca extremitatile muchiei fac parte din arbori diferiti, vom uni cei 2 arbori din care fac parte extremitatile muchiei. Apoi, adunam costul acestei muchii la costul total (construind suma minima necesara).
 Pentru a uni cei 2 arbori, trebuie sa iteram prin toate punctele si sa schimbam valoarea capatului y cu valoarea capatului x. Daca avem arcul (x, y) inseamna ca vrem sa unim arborele x cu arborele y. Arborele x va avea elemente cu valoarea x, iar arborele y cu elemente de valoare y. Ca arborii x si y sa fie aceeasi, schimbam valorile de y cu x :D
 
 La final, afisam suma minima, numarul muchiilor si toate muchiile pe care le-am gasit si care formeaza arborele partial de cost minim.
 
 Cu aceasta abordare am primit 50 de puncte pentru ca sortam muchiile in O(n), iar apoi le-am sortat in O(n * log n) si am primit 70 de puncte.
 
 E ok cum am inteles algoritmul? Practic el mereu va forma un arbore de cost minim, atat timp cat pornim iterarea muchiilor de la cele cu costul minim.
 
 Solutia actuala are complexitatea de O(nlogn) - pt sortare + O(n * m) - pt a itera toate muchiile (m) si pt a uni arborii de fiecare data.
 
 
 
 */