#include <fstream>
#include <algorithm>

using namespace std;

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

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

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
        tata[x]=atata(tata[x]);
}
inline void rezolvare (int i)
{
    int p1,p2;
   for (i=1;i<=m;i++)
   {
       p1=atata(tata[v[i].x]);
       p2=atata(tata[v[i].y]);
       if (p1!=p2)
       {
           nrm++;
           sum+=v[i].cost;
           v[i].viz=1;
           tata[v[i].x]=p2;
           if (nrm==n-1)
            break;
       }
   }
}
inline void afisare (int i)
{
    i=0;
    fout<<sum<<endl<<nrm<<endl;
    for (int j=1;j<=m;j++)
    {
        if (v[j].viz==1)
        {
            i++;
            fout<<v[j].x<<" "<<v[j].y<<endl;
        }
        if (i==nrm)
            break;
    }
}

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