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

using namespace std;

int n,m,nr_muchii,grupa[2000000],cost_total;
queue < pair<int,int> > muchii_finale;

struct muchie
{
    int nod1, nod2, cost;
}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;
    return aflare_grupa(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;
    sort(v,v+m,comp);
    for(i=1;i<=n;i++)
        grupa[i]=i;
    i=0;
    do
        {
			if(aflare_grupa(v[i].nod1)!=aflare_grupa(v[i].nod2))
				{
				    nr_muchii++;
                    cost_total+=v[i].cost;
                    muchii_finale.push(make_pair(v[i].nod1,v[i].nod2));
                    reuniune(v[i].nod1,v[i].nod2);
				}
			i++;
        }while(nr_muchii<n-1);
    g<<cost_total<<endl<<nr_muchii<<endl;
    int nr=0;
    while(!muchii_finale.empty())
    {
        g<<muchii_finale.front().first<<" "<<muchii_finale.front().second<<endl;
        muchii_finale.pop();
    }
    return 0;
}