#include <fstream>
#include <algorithm>

using namespace std;

ifstream fin("apm.in");
ofstream fout("apm.out");

struct muchie{
    int x,y,cost;
}v[400002];

struct sol{
    int a,b;
}z[200002];

int n,m,tata[200002],sum,nrm;

bool cum (muchie a, muchie b)
{
    return a.cost < b.cost;
}
inline void citire ()
{
    fin>>n>>m;
    for (int i=1;i<=m;i++)
        fin>>v[i].x>>v[i].y>>v[i].cost;
    for (int i=1;i<=n;i++)
        tata[i]=i;
    sort (v+1,v+m+1,cum);
}
int atata (int x)
{
    if (x==tata[x])
        return x;
    else
        return tata[x]=atata(tata[x]);
}
inline void rezolvare (int i)
{
    int p1,p2;
   for (i=1;i<=m;i++)
   {
       p1=atata(v[i].x);
       p2=atata(v[i].y);
       if (p1!=p2)
       {
           nrm++;
           sum+=v[i].cost;
           tata[p1]=p2;
           z[nrm].a=v[i].x;
           z[nrm].b=v[i].y;
           if (nrm==n-1)
            break;
       }
   }
}
inline void afisare (int i)
{

    fout<<sum<<endl<<nrm<<endl;
    for (i=1;i<=nrm;i++)
        fout<<z[i].a<<" "<<z[i].b<<endl;
}

int main()
{
    int i=0;
    citire();
    rezolvare(i);
    afisare (i);
    fin.close();
    fout.close();
    return 0;
}