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

using namespace std;

int n, m, comp[1010], suma;
struct muchii
{
    int x, y, cost;
};
vector <muchii> a, sol;

inline void Read()
{
    ifstream f("apm.in");
    f>>n>>m;
    int i;
    muchii aux;
    for (i = 1; i<=m; i++)
    {
        f>>aux.x>>aux.y>>aux.cost;
        a.push_back(aux);
    }
    f.close();
}

inline bool cmp(const muchii A, const muchii B)
{
    return A.cost < B.cost;
}

inline void Unire(int x, int y)
{
    int i;
    for (i=1; i<=n; i++)
        if (comp[i] == y)
            comp[i] = x;
}

inline void Kruskal()
{
    sort(a.begin(), a.end(), cmp);
    int n1, i, nrm, x, y, cost;
    n1 = n - 1;

    for (i=1; i<=n; i++)
        comp[i] = i;

    vector <muchii>::iterator it, final;
    muchii aux;
    it = a.begin();
    final = a.end();
    nrm = 0;
    while (nrm!=n1 && it!=final)
    {
        aux = *it;
        it++;
        x = aux.x;
        y = aux.y;
        cost = aux.cost;
        if (comp[x] != comp[y])
        {
            nrm++;
            if (comp[x] < comp[y])
                Unire(comp[x], comp[y]);
            else
                Unire(comp[y], comp[x]);
            suma += cost;
            sol.push_back(aux);
        }
    }
}

inline void Write()
{
    ofstream g("apm.out");
    g<<suma<<"\n";
    vector <muchii>::iterator it;
    muchii aux;
    g<<sol.size()<<"\n";
    for (it = sol.begin(); it!=sol.end(); it++)
    {
        aux = *it;
        g<<aux.x<<" "<<aux.y<<"\n";
    }
    g.close();
}

int main()
{
    Read();
    Kruskal();
    Write();
    return 0;
}