#include <iostream>
#include <fstream>
#include <queue>
#include <vector>

using namespace std;

int n,m,tata[200005],greu[200005],cost,nsol;
vector<pair<int,int> >sol;
struct muchie
{
    int x,y,c;
    bool operator<(muchie b) const
    {
        return c>b.c;
    }
};
priority_queue<muchie,vector<muchie> >q;

void citire()
{
    ifstream fin("apm.in");
    fin>>n>>m;
    int x,y,c;
    for(int i=0;i<m;i++)
    {
        fin>>x>>y>>c;
        muchie nou;
        nou.x=x;
        nou.y=y;
        nou.c=c;
        q.push(nou);
    }
}

void radacina(int nod,int &rad)
{
    rad=nod;
    while(tata[rad]!=rad)
        rad=tata[rad];
}

void kruskal()
{
    for(int i=1;i<=n;i++)
    {
        tata[i]=i;
        greu[i]=1;
    }
    while(nsol<n-1&&!q.empty())
    {
        muchie nou;
        nou=q.top();
        q.pop();
        int radx,rady;
        radacina(nou.x,radx);
        radacina(nou.y,rady);
        if(radx!=rady)
        {
            cost+=nou.c;
            nsol++;
            sol.push_back(make_pair(nou.x,nou.y));
            if(greu[radx]>=greu[rady])
            {
                tata[rady]=radx;
                if(greu[radx]<greu[rady]+1)
                    greu[radx]=greu[rady]+1;
            }
            else
            {
                tata[radx]=rady;
                if(greu[rady]<greu[radx]+1)
                    greu[rady]=greu[radx]+1;
            }
        }
    }
}

void afisare()
{
    ofstream fout("apm.out");
    fout<<cost<<"\n"<<n-1<<"\n";
    for(int i=0;i<n-1;i++)
        fout<<sol[i].first<<" "<<sol[i].second<<"\n";
}

int main()
{
    citire();
    kruskal();
    afisare();
    return 0;
}