#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],rg[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)
{
    while (tata[x]!=x)
        x=tata[x];
    return x;
}
void unire (int x, int y)
{
    if (rg[x]>rg[y])
        tata[x]=y;
    if (rg[x]<rg[y])
        tata[y]=x;
    if (rg[x]==rg[y])
    {
        rg[x]++;
        tata[x]=y;
    }
}
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;
           unire (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;
}