#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <tuple>
#include <list>
#include <algorithm>
 
#define Nmax 100001
 
using namespace std;
 
ifstream fin("apm.in");
ofstream fout("apm.out");
 
int N, M;
 
struct elem
{
    int x, y, c;
};
elem graf_ponderat[4*Nmax], apm[2*Nmax];
 
int tata[2*Nmax], rang[2*Nmax];
int S;

class Graf{
private:
    int Nr_Noduri, Nr_Muchii;
    vector<int> GRAF[Nmax]; // lista de adiacenta
    // pair< int, pair<int,int> > graf_ponderat[400010];   // lista de adiacenta pentru graf ponderat
 
public:
    Graf(int N, int M); // constructor
    void Citire_Graf_Neorientat_Ponderat();
    void Kruskal();
};
 
// constructor
Graf :: Graf(int N, int M)
{
    Nr_Noduri = N;
    Nr_Muchii = M;
}
 
inline bool cmp(const elem &a, const elem &b)
{
    return a.c < b.c;
}
 
void Graf :: Citire_Graf_Neorientat_Ponderat()
{
    for ( int i = 1; i <= Nr_Muchii; i++ )
    {
        fin >> graf_ponderat[i].x;
        fin >> graf_ponderat[i].y;
        fin >> graf_ponderat[i].c;
    }
    // se ordoneaza muchiile grafului crescator dupa cost
    sort(graf_ponderat+1, graf_ponderat+Nr_Muchii+1, cmp);
}
 
// functie care verifica tatal unui nod
int Verificare_Tata(int nod)
{
    // aceasta cautare se termina cand tatal nodului curent este nodul curent
    while ( tata[nod] != nod )
        nod = tata[nod];
    return nod;
}

void Unire(int x, int y)
{
    x = Verificare_Tata(x);
    y = Verificare_Tata(y);
    // unim nodurile in functie de rangul acestora
    // intotdeauna legam subarborele mai mic de cel mai mare
    if ( rang[x] < rang[y] )
        tata[x] = y;

    if ( rang[x] > rang[y] )
        tata[y] = x;

    if ( rang[x] == rang[y] )
    {
        tata[x] = y;
        rang[y]++; 
    }
}

void Graf :: Kruskal()
{
    int k = 0;
    // pentru fiecare nod din graf vom memora reprezentantul sau 
    // (de fapt al subarborelui din care face parte)
    // folosim tabloul unidimensional tata
    for ( int i = 1; i <= Nr_Noduri; i++ )
    {
        tata[i] = i;
        rang[i] = 1;
    }
 
    // determinare APM
    for ( int i = 1; i < Nr_Muchii; i++ )
    {
        // daca extremitatile muchiei fac parte din subarbori diferiti,
        // acestia se vor reuni, iar muchia respectiva face parte din APM
        if ( Verificare_Tata(graf_ponderat[i].x) != Verificare_Tata(graf_ponderat[i].y) )
        {
            Unire(Verificare_Tata(graf_ponderat[i].x), Verificare_Tata(graf_ponderat[i].y) );

            apm[++k] = graf_ponderat[i];
            // adunam costul total al arborelui 
            S += graf_ponderat[i].c;
        }
    }
 
    // afisare
    fout << S << '\n' << Nr_Noduri-1 << '\n';
    for ( int i = 1; i <= k; i++ )
        fout << apm[i].x << " " << apm[i].y << '\n';
}
 
int main()
{
    fin >> N >> M;
    Graf G(N, M);
    G.Citire_Graf_Neorientat_Ponderat();
    G.Kruskal();
 
    return 0;
}