#include <fstream>
#include<algorithm>

using namespace std;

ifstream cin("apm.in");
ofstream cout("apm.out");

struct ura
{
    int nod1,nod2,cost;
}v[400001];

bool viz[400001];
int sef[200001];

bool cmp(ura a, ura b)
{
    return (a.cost<b.cost);
}

int sefsuprem (int nod)
{
    if(sef[nod]==nod)
        return nod;
    else
        return sef[nod]=sefsuprem(sef[nod]);
}
void unire(int nod1, int nod2)
{
    int sef1=sefsuprem(nod1);
    int sef2=sefsuprem(nod2);
    sef[sef2]=sef1;
}


int main()
{
    int n,m,i,nrm,s;
    cin>>n>>m;
    for(i=1;i<=m;i++)
        cin>>v[i].nod1>>v[i].nod2>>v[i].cost;
    sort (v+1,v+m+1,cmp);

    for(i=1;i<=n;i++)
        sef[i]=i;
    nrm=0;
    s=0;
    for(i=1;i<=m && nrm<n-1;i++)
        if(sefsuprem(v[i].nod1) != sefsuprem(v[i].nod2))
        {
            unire(v[i].nod1,v[i].nod2);
            s+=v[i].cost;
            nrm++;
            viz[i]=1;
        }
    cout<<s<<"\n"<<n-1<<"\n";
    for(i=1;i<=m;i++)
        if(viz[i]==1)
            cout<<v[i].nod1<<" "<<v[i].nod2<<"\n";

    return 0;
}