#include <iostream>
#include<fstream>
#include<algorithm>
#include<vector>
using namespace std;

ifstream fin("apm.in");
ofstream fout("apm.out");
int n,m;
struct muchie{
    int x,y,cost;
};

bool cmp(muchie m1, muchie m2){
    return m1.cost < m2.cost;
}

int *radacini;
vector<muchie> muchii;

int radacina(int nod){
    if(radacini[nod]==nod)
        return nod;
    return radacini[nod]=radacina(radacini[nod]);
}

int uneste(int x, int y){
    radacini[radacina(x)]=radacina(y);
}

int main()
{
    fin>>n>>m;
    muchii=vector<muchie>(m);
    radacini = new int[n+1];
    for(int i=1;i<=n;i++)
        radacini[i]=i;

    int x,y,cost;
    for(int i=0;i<m;i++){
        fin>>x>>y>>cost;
        muchii[i].x=x;
        muchii[i].y=y;
        muchii[i].cost=cost;
    }

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

    int costMin=0;
    vector<muchie> solutie;

    for(muchie m : muchii){
        int radacina1 = radacina(m.x);
        int radacina2 = radacina(m.y);
        cout<<m.x<<" "<<m.y<<endl;
        if(radacina1==radacina2)
            continue;

        costMin+=m.cost;
        solutie.push_back(m);

        uneste(radacina1, radacina2);
    }

    cout<<costMin<<"\n";
    cout<<n-1<<"\n";
    for(muchie m : solutie)
        cout<<m.x<<" "<<m.y<<"\n";

    return 0;
}