///Versiunea O(m * log n)

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

using namespace std;

ifstream f("grafpond.in");
ofstream g("grafpond.out");

vector< pair<int,int> >apm;

int n , m , r[200001]; //pentru fiecare nod voi sti reprezentantul grafului partial din care face parte

struct muchie{
    int x,y,cost;
};

muchie vm[400001];

bool cmp (muchie a, muchie b)
{
    return a.cost < b.cost;
}

int main()
{
    int s = 0, r1, r2;

    f >> n >> m;

    for(int i = 0; i < m; i++)
        f >> vm[i].x >> vm[i].y >> vm[i].cost;

    sort(vm, vm + m, cmp);  //sortez vectorul de muchii crescator dupa cost

    for(int i =1 ; i <= n ; i++)
        r[i] = i;   //initial fiecare nod reprezinta un graf partial independent

  //  g<<"APM ul grafului este:"<<'\n';

    for(int i = 0; i < m; i ++)  //parcurg muchiile in ordine cresc si incerc sa le adaug la solutie
        if(r[vm[i].x] != r[vm[i].y]) // daca nodurile muchiei i fac parte din subrabori diferiti atunci legam subarborii
        {
            s += vm[i].cost;
            apm.push_back ( make_pair(vm[i].x, vm[i].y));

            //legam subarborii
            r1 = r[vm[i].x];
            r2 = r[vm[i].y];

            for(int j =1; j <= n; j++)
                if(r[j] == r1)
                    r[j] = r2;
        }

  //  g <<'\n'<< "cu costul "<<'\n'<< s << '\n';

    g<<s<<'\n'<<apm.size()<<'\n';

    for( auto elem =apm.begin(); elem != apm.end(); elem++)
        g<<(*elem).first<<" " << (*elem).second<< '\n';
    return 0;
}