#include <iostream>
#include <algorithm>
#include <vector>
#include <fstream>

using namespace std;

struct muchie /// practic este structura in care memorez muchiile
{
    int x,y,c;  /// x- primul nod, y al doilea nod, c- cost
};

int tata[100], h[100]; /// vector de tata pentru memorarea arborelui de reprezentati, h pentru inaltimea arborelor
vector < muchie > E; /// vectorul de muchii dat din fisier
vector < muchie > apcm; /// aici salvez arborele partial de cost minim


bool cmp( muchie A, muchie B)
{
    return A.c < B.c;
}

int reprezentant(int x)   /// calculez reprezentatul
{
    if (tata[x]==x) /// reprezentatul va fi varful arborelui, astfel daca tata[x] = x inseamna ca x e vf arborelui si am gasit reprezentatul
        return x;
   tata[x] = reprezentant((tata[x]));
   return tata[x];
}

void reuneste(int x, int y)  /// reunesc arborele de reprezentanit==ti
{
    int r1 = reprezentant(x);   /// r1 - varful arborelui din care face parte x
    int r2 = reprezentant(y);  /// r2 - varful arborelui din care face parte y
    if (h[r1] < h[r2])       /// daca inaltimea arborelui(x) < cea a aarborelui(y), atunci unesc arborele mai mic la cel mai mare, pentru a obtine o lungime minima a arborelui nou format
        tata[r1] = r2;  /// deci unesc arborele(x) de reprezentatul(radacina arb.) lui y
    else if (h[r1] > h[r2]) /// la fel si aici
        tata[r2] = r1;
    else
    {
        tata[r1] = r2; /// daca sunt egale nu conteaza pe care de care il leg
        h[r2]++;   /// si inaltimea creste cu 1
    }
}

//void Kruskal

int main()
{
    int n,m,suma = 0;
    ifstream fin("apm.in");
    ofstream fout("apm.out");
    fin >> n >> m;
    E.resize(m); /// dam resize si automat toate valorile E[i] devin 0, e mai usor pentru ca nu dam de fiecare data pushback, pentur a mari vectorul
    for ( int i = 0 ; i < m; i++)
        fin >>  E[i].x >> E[i].y >> E[i].c; /// introducem primul si al 2 nod al muchii, costul
    sort (E.begin(), E.end(), cmp);      /// sortam muchiile pentru a obtine arbore de cost minim
    for ( int i = 0 ; i < n; i++)
        tata[i] = i;            /// initializam practic fiecare nod ca o componente conexa
    for ( int i = 0; ((i < m) && ((int)apcm.size() < n-1)); i++)
    {
        muchie temp = E[i];
        if (reprezentant(temp.x) != reprezentant(temp.y))  /// daca reprezentatii nodurilor sunt diferiti, adica din 2 componente conexe diferite
        {
            reuneste(temp.x, temp.y);              /// reunesc arborele de reprezentanti
            apcm.push_back(temp);                  /// aleg muchia data in apcm meu
        }
    }
    for (int i = 0 ; i < (int)apcm.size(); i++) /// verific muchiile care le-a ales
    {
        suma = suma + apcm[i].c;
    }
    fout << suma << endl << (int)apcm.size() << endl;
    for ( auto a:apcm)   /// o alta metoda de citire a datelor din vector
        fout << a.x << " " << a.y << endl;
    fin.close();
    fout.close();
    return 0;
}