#include <fstream>
#include <queue>
using namespace std;
ifstream f("kruskal.in");
ofstream g("kruskal.out");
struct muchie
{
    int n1,n2,cost;
}a,mcrt,arbore[200005];
int n,m,tata[200005],nrm,rang[200005],r1,r2;
long s;
struct comp
{
    bool operator() (muchie i, muchie j)
    {
        return i.cost>j.cost;
    }
};
priority_queue<muchie,vector<muchie>,comp>coada;
void citire()
{ int x,y,z,i;
    f>>n>>m;
    for(i=1;i<=n;i++)
        {tata[i]=i;rang[i]=1;}
    for(i=1;i<=m;i++)
       {f>>x>>y>>z;
       a.n1=x;
       a.n2=y;
       a.cost=z;
       coada.push(a);
       }
}
int radacina(int x)
{
    int r=x;
    while(tata[r]!=r)r=tata[r];
    while(tata[x]!=x)
        {
            int aux=x;
            x=tata[x];
            tata[aux]=r;
        }
        return r;
    }
void kruskal()
{
    while(!coada.empty() && nrm<n-1)
    {
        mcrt=coada.top();
        coada.pop();
        r1=radacina(mcrt.n1);
        r2=radacina(mcrt.n2);
        if(r1!=r2)
        {
            if(rang[r1]>rang[r2])
                tata[r2]=r1;
            else tata[r1]=r2;
            if(rang[r1]==rang[r2])rang[r2]++;
            nrm++;
            arbore[nrm]=mcrt;
            s=s+mcrt.cost;
        }

    }
}
void afisare()
{
    g<<s<<'\n';
    g<<nrm<<'\n';
    for(int i=1;i<=nrm;i++)
        g<<arbore[i].n1<<" "<<arbore[i].n2<<'\n';
}
int main()
{ citire();
kruskal();
afisare();
    return 0;
}