#include <queue>
#include <vector>
#define LE 400600
#define pb push_back
#include <cstdio>

using namespace std;
int n,m,k,i,j,viz[LE],t,x,y,rez,co;
vector <int> H[LE],HC[LE];
struct trei{
	int nod,cost,sursa;
}Top,V[LE],E;
struct cmp
{
	bool operator ()(trei A,trei B)
	{
		return A.cost>B.cost;
	}
	
};
priority_queue<trei,vector<trei>,cmp> dolar;

void NodePush(int nu)
{
	viz[nu]=true;
	
	for(t=0;t<H[nu].size();++t)
	   if(viz[H[nu][t]]==false)
	     {
		  E.nod=H[nu][t]; E.cost=HC[nu][t]; E.sursa=nu;	
	      dolar.push(E);
		 }
}
int main()
{
	freopen("apm.in","r",stdin);
	freopen("apm.out","w",stdout);
	scanf("%ld%ld",&n,&m);
	
	for(i=1;i<=m;++i)
	{
		scanf("%ld%ld%ld",&x,&y,&co);
		H[x].pb(y);H[y].pb(x);
		HC[x].pb(co);HC[y].pb(co);
	}
	
	NodePush(1);
	
	while (!dolar.empty())
	{
		Top=dolar.top(); 
		dolar.pop();
		if (viz[Top.nod]==false) {
			rez+=Top.cost;V[++k]=Top;
			NodePush(Top.nod);
			
		}
	}
   
	printf("%d\n%d\n",rez,k);
	
	for(i=1;i<=k;++i)
		printf("%d %d%\n",V[i].sursa,V[i].nod);
	
	return 0;
}