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

using namespace std;

struct muchie
{
  int x,y,c;
}e;

int n,m,root[200001],rang[200001];

bool comp(muchie m1,muchie m2)
{
    return (m1.c < m2.c);
}

vector<muchie> M,APM;

void join(int n1,int n2)
{
	if(rang[n1]>rang[n2]) root[n2]=n1;
	else root[n1]=n2;
	if(rang[n1]==rang[n2]) rang[n2]++;
}
int find(int x)
{
	int aux,y;
	aux=x;
	while(root[aux]!=aux)
		aux=root[aux];
	while(root[x]!=x)
	{
		y=root[x];
		root[x]=aux;
		x=y;
	}
	return aux;
}

int main()
{
    ifstream f("apm.in");
	ofstream g("apm.out");
    int i,p,q,r,nm=0,apmroot,apmcost=0;
    f>>n>>m;

    for(i=1;i<=m;i++)
    {
        f>>p>>q>>r;
        e.x=p;
        e.y=q;
        e.c=r;
        M.push_back(e);
    }
    for(i=1;i<=n;i++)
	{
			root[i]=i;
			rang[i]=1;
	}
    sort(M.begin(),M.end(),comp);

    vector<muchie>::iterator it=M.begin();
    APM.push_back(*it);
    join((*it).x,(*it).y);
    apmcost+=(*it).c;
    nm=1;//Nr de muchii din APM
    it++; //A doua muchie

    while(nm < n-1 && it!=M.end())
    {
        e.x=(*it).x;
        e.y=(*it).y;
        e.c=(*it).c;
        if(find(e.x) != find(e.y))
        {
            APM.push_back(e);
            join(e.x,e.y);
            apmcost+=e.c;
            nm++;
        }
        it++;
    }
    //cout<<"Cost APM: "<<apmcost<<endl;
    //cout<<"Arborele Partial de Cost Minim este format din muchiile: \n";
	g<<apmcost<<endl;
	g<<APM.size()<<endl;
    for(vector<muchie>::iterator it2=APM.begin();it2!=APM.end();it2++)
    {
        g<<(*it2).x<<" "<<(*it2).y;
        g<<"\n";
    }

    f.close();
    return 0;
}