#include <fstream>
#include <algorithm>
using namespace std;

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

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

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

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 findt (int nod)
{
    while (nod!=tata[nod])
    {
        nod=tata[nod];
        tata[nod]=tata[tata[nod]];
    }
    return nod;
}

inline void unire (int a,int b)
{
    if (rg[a]>rg[b])
        tata[b]=a;
    if (rg[b]>rg[a])
        tata[a]=b;
    if (rg[b]==rg[a])
    {
        tata[a]=b;
        rg[a]++;
    }
}

inline void rezolvare ()
{
    int i,p1,p2;
    for (i=1;i<=m;i++)
    {
        p1=findt(v[i].x);
        p2=findt(v[i].y);
        if (p1!=p2)
        {
            sum+=v[i].cost;
            sol[++nrm]=i;
            unire(p1,p2);
            if (nrm==n-1)
                break;
        }
    }
}

inline void afisare ()
{
    fout<<sum<<endl<<nrm<<endl;
    for(int i=1;i<=nrm;i++)
        fout<<v[sol[i]].x<<" "<<v[sol[i]].y<<endl;
}

int main()
{
    citire();
    rezolvare ();
    afisare ();
    return 0;
}