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

using namespace std;

int n, m, comp[200010], 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 int find(int x)
{
    int r, y;
    r = x;
    while (comp[r] > 0)
        r = comp[r];

    while (comp[x] > 0)
    {
        y = comp[x];
        comp[x] = r;
        x = y;
    }

    return r;
}

inline void unite (int x, int y)
{
    if (comp[x] < comp[y])
    {
        comp[x] += comp[y];
        comp[y] = x;
    }
    else
    {
        comp[y] += comp[x];
        comp[x] = y;
    }
}

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] = -1;

    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;
//        cout<<aux.x<<" "<<aux.y<<" "<<aux.cost<<"\n";
//      if (comp[x] != comp[y])
        if (find(x) != find(y)) // daca nu sunt unite multimile din care fac parte x si y atunci le unesc
        {
//            cout<<aux.x<<" "<<aux.y<<" "<<aux.cost<<"\tfind(X) = "<<find(x)<<" find(Y)="<<find(y)<<"\n";
            nrm++;
//            if (comp[x] < comp[y])
//                Unire(comp[x], comp[y]);
//            else
//                Unire(comp[y], comp[x]);
            unite(find(x), find(y));
            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;
}