//#include <fstream>
//#include <iostream>
//#include <vector>
//#include <algorithm>
//
//using namespace std;
//
//struct edge
//{
//	int x,y,cost;
//};
//
//bool costCmp(edge a, edge b)
//{
//	return a.cost<b.cost;
//}
//
//int T[200005],R[200005];
//
//int find(int x)
//{
//	while(T[x])
//		x=T[x];
//	return x;
//}
//void join(int x,int y)
//{
//	int a=find(x),b=find(y);
//	if(R[a]>R[b])
//		T[b]=a;
//	else T[a]=b;
//	if(R[a]==R[b]) R[b]++;
//}
//
//
//int main()
//{
//	ifstream f("apm.in");
//	ofstream g("apm.out");
//
//	vector<edge> G,APM;
//	int N,M,i,x,y,c,apmcost=0;
//	edge e;
//	f>>N>>M;
//	for(i=1;i<=M;i++)
//	{
//		f>>x>>y>>c;
//		e.x=x;
//		e.y=y;
//		e.cost=c;
//		G.push_back(e);
//	}
//	sort(G.begin(),G.end(),costCmp);
//
//	for(i=1;i<=N;i++)
//	{
//		T[i]=0;
//		R[i]=1;
//	}
//
//	vector<edge>::iterator it;
//
//	while(APM.size() < N-1)
//	{
//		it=G.begin();
//
//
//
//		while(find(it->x) != find(it->y)) it++;
//
//
//
//		APM.push_back(*it);
//
//
//		join(it->x,it->y);
//
//		apmcost += (it->cost);
//		//G.erase(it);
//	}
//	g<<apmcost<<"\n"<<N-1<<"\n";
//	for(it=APM.begin();it!=APM.end();it++)
//	{
//		g<<it->x<<" "<<it->y<<"\n";
//	}
//
//	f.close();
//	g.close();
//	return 0;
//}

#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(find((*it).x),find((*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(find(e.x),find(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;
}