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

using namespace std;

const int MAX=40001;

int tata[MAX], h[MAX];

struct muchie
{
    int a, b, cost;
};

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

int comp(int a)
{
    if(tata[a]!=0){
        int c=comp(tata[a]);
        tata[a]=c;
        return c;
    }

    return a;
}

void uneste(int ca, int cb)
{
    if(h[ca]>h[cb]){
        tata[cb]=ca;
    }else{
        tata[ca]=cb;

        if(h[ca]==h[cb])
            h[cb]++;
    }
}

int main()
{
    ifstream fin("apm.in");
    ofstream cout("apm.out");

    int n, m, i, j, k, c1, c2;
    fin>>n>>m;

    vector<muchie> muchii(m);
    vector<muchie> arbore;

    for(i=0;i<m;i++)
        fin>>muchii[i].a>>muchii[i].b>>muchii[i].cost;

    sort(muchii.begin(), muchii.end(), compara_muchii);

    int cost=0;
    j=0;
    for(i=1;i<=n-1;i++){
        c1=comp(muchii[j].a);
        c2=comp(muchii[j].b);
        while(c1==c2){
            j++;
            c1=comp(muchii[j].a);
            c2=comp(muchii[j].b);
        }

        cost+=muchii[j].cost;
        arbore.push_back(muchii[j]);

        uneste(c1, c2);
    }

    cout<<cost<<"\n"<<n-1<<"\n";

    for(i=0;i<arbore.size();i++)
        cout<<arbore[i].a<<" "<<arbore[i].b<<"\n";

    return 0;
}