#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <tuple>
#include <list>
#include <algorithm>

#define Nmax 100005
#define Nmax2 200002

using namespace std;

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

int N, M;

struct elem
{
    int x, y, c;
}graf_ponderat[400002];

struct elem2
{
    int X, Y;
}apm[Nmax2];

int tata[Nmax2];

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);
}

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;

    // determinare APM
    int S = 0, cnt = 0;
    for ( int i = 0; i < Nr_Muchii && cnt < Nr_Noduri; i++ )
    {
        // daca extremitatile muchiei fac parte din subarbori diferiti,
        // acestia se vor reuni, iar muchia respectiva face parte din APM
        if ( tata[graf_ponderat[i].x] != tata[graf_ponderat[i].y] )
        {
            // adunam costul total al arborelui 
            S += graf_ponderat[i].c;
            ++k;
            apm[k] = { graf_ponderat[i].x, graf_ponderat[i].y };

            // reunim subarborii
            int ai = tata[graf_ponderat[i].x];
            int aj = tata[graf_ponderat[i].y];
            for ( int j = 1; j <= Nr_Noduri; j++ )
                if ( tata[j] == aj )
                    tata[j] = ai;
        }
    }

    // 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;
}