#include <fstream>
#include <algorithm>

using namespace std;

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

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

int 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;
    i=1;
    while (nrm<n-1)
    {
       p1=atata(v[i].x);
       p2=atata(v[i].y);
       if (p1!=p2)
       {
           sum+=v[i].cost;
           tata[p1]=p2;
           z[++nrm]=i;
       }
       i++;
    }
}
inline void afisare (int i)
{

    fout<<sum<<endl<<nrm<<endl;
    for (i=1;i<=nrm;i++)
        fout<<v[z[i]].x<<" "<<v[z[i]].y<<endl;
}

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