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

struct muchie
{
    int a; //Sursa
    int b; //Destinatie
    int cost; //Cost
    bool apartine_apm; //Daca muchia apartine APM
};

int n; //Nr. de varfuri
int m; //Nr. de muchii
muchie muchii[400001]; //Muchiile
int cost_apm; //Costul arborelui
int noduri[200001]; //Componenta de care apartine fiecare nod
list<int> componente[200001]; //Componentele conexe

inline bool comparare_muchii(muchie a, muchie b)
{
    if (a.cost < b.cost)
        return true;
    else
        return false;
}
inline void citire()
{
    ifstream fin("apm.in");
    fin >> n >> m;
    for (int i = 0; i < m; i++)
    {
        fin >> muchii[i].b >> muchii[i].a >> muchii[i].cost;
        muchii[i].apartine_apm = false;
    }
    fin.close();
}
inline void kruskal()
{
    cost_apm = 0;
    for (int i = 1; i <= n; i++)
	{
        noduri[i] = i; //Fiecare nod e o componenta conexa
		componente[i].push_back(i); //Fiecare componenta are un nod
	}
    sort(&muchii[0], &muchii[m], comparare_muchii); //Sortam muchiile dupa cost
    int c_muchie = 0; //Contorul in vectorul de muchii
    int muchii_adaugate = 0; //Nr. de muchii din APM
    int c_modificata; //Valoarea componentei celui de-al doilea nod al muchiei
	int c_atribuita; //Valoarea componentei primului nod al muchiei
	list<int>::iterator it_modificat;
    while (muchii_adaugate < (n - 1))
    {
        //APM-ul are n-1 muchii
        if (noduri[muchii[c_muchie].a] != noduri[muchii[c_muchie].b])
        {
            //Daca muchia contine noduri din noduri diferite, aceasta poate fi adaugata
            c_modificata = noduri[muchii[c_muchie].b]; //Componenta modificata este extremitatea muchiei
			c_atribuita = noduri[muchii[c_muchie].a]; //Componenta la care va fi adaugat
            cost_apm = cost_apm + muchii[c_muchie].cost; //Modificam costul arborelui
            muchii[c_muchie].apartine_apm = true; //Muchia apartine APM
            muchii_adaugate++; //Incrementam numarul de muchii al APM
			componente[c_atribuita].insert(componente[c_atribuita].end(), componente[c_modificata].begin(), componente[c_modificata].end());
			it_modificat = componente[c_modificata].begin();
			while (it_modificat != componente[c_modificata].end())
			{
				noduri[*it_modificat] = c_atribuita;
				it_modificat++;
			}
			componente[c_modificata].clear();
		}
        c_muchie++;
    }
}
inline void scriere()
{
    ofstream fout("apm.out");
    fout << cost_apm << "\n" << n-1 << "\n";
    for (int i = 0; i < m; i++)
        if (muchii[i].apartine_apm == true)
            fout << muchii[i].a << " " << muchii[i].b << "\n";
    fout.close();
}
int main()
{
    citire();
    kruskal();
    scriere();
    return 0;
}