#include<iostream>
#include<fstream>
#include<algorithm>

using namespace std;

int n,m,nr_muchii,grupa[2000000],cost_total;

struct muchie
{
    int nod1, nod2, cost,sem;
}v[2000000];

int comp(muchie x,muchie y)
{
    if(x.cost<y.cost)
        return 1;
    return 0;
}

int aflare_grupa(int i)
{
    if(grupa[i]==i)
        return i;
    grupa[i]=aflare_grupa(grupa[i]);
    return grupa[i];
}
void reuniune (int i,int j)
{
    grupa[aflare_grupa(i)]=aflare_grupa(j);
}
int main()
{
    ifstream f("apm.in");
    ofstream g("apm.out");
    f>>n>>m;
    int i;
    for(i=0;i<m;i++)
    {
        f>>v[i].nod1>>v[i].nod2>>v[i].cost;
        v[i].sem=0;
    }
    sort(v,v+m,comp);
    for(i=1;i<=n;i++)
        grupa[i]=i;
    i=0;
    do
        {
			while(aflare_grupa(v[i].nod1)==aflare_grupa(v[i].nod2))
				i++;
			nr_muchii++;
			cost_total+=v[i].cost;
			v[i].sem=1;
			reuniune(v[i].nod1,v[i].nod2);
			i++;
        }while(nr_muchii<n-1);
    g<<cost_total<<endl<<nr_muchii<<endl;
    for(i=0;i<m;i++)
        if(v[i].sem)
        g<<v[i].nod1<<" "<<v[i].nod2<<endl;
    return 0;
}