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

using namespace std;
ifstream f("apm.in");
ofstream g("apm.out");
int  n,m,k,i,j,t,x,y,rez,co;
vector <short int > H[LE],HC[LE];
short int viz[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()
{
	f>>n>>m;
	for(i=1;i<=m;++i)
	{
		f>>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);
			
		}
	}
  */ 
	g<<rez<<'\n'<<k<<'\n';
	
	for(i=1;i<=k;++i)
		g<<V[i].sursa<<" "<<V[i].nod<<'\n';
	
	return 0;
}