#include<fstream>
#include<vector>
#include<queue>
using namespace std;
ifstream in("apm.in");
ofstream out("apm.out");
const int N=200010;
const int INF=1000000000;

priority_queue<pair<int,int> > h;
int n,m,d[N],pred[N];
struct per{int nod,cost;};
vector<per>a[N];
bool s[N];

void read()
{
	in>>n>>m;
	int x,y,z;
	for(int i=1;i<=m ;i++)
	{
		in>>x>>y>>z;
		a[x].push_back((per){y,z});
		a[y].push_back((per){x,z});
	}
}
void init()
{
	for(int i=0;i<N;i++)
		d[i]=INF;
}
int vmin()
{
	while(!h.empty())
	{
		if(!s[h.top().second])
			return h.top().second;
		h.pop();
	}
	return 0;
}
void actualizare(int x)
{
	int c,y;
	for(size_t i=0 ; i<a[x].size() ; i++)
	{
		y = a[x][i].nod;
		c = a[x][i].cost;
		if(s[y])
			continue;
		if( c < d[y])
		{
			d[y] = + c;
			pred[y]=x;
			h.push(make_pair(-d[y],y));
		}
	}
}

void f(int param)
{
	int x;
	d[param]=0;
	h.push(make_pair(d[param],param));
	for(int i=1;i<n;i++)
	{
		x=vmin();
		s[x]=true;
		actualizare(x);
	}
}
void afis()
{
	int sum=0;
	for(int i=2;i<=n;i++)
		sum+=d[i];
	out<<sum<<"\n"<<n-1<<"\n";
	for(int i=2;i<=n;i++)
		out<<i<<" "<<pred[i]<<"\n";
}
int main()
{
	read();
	init();
	f(1);
	afis();
	return 0;
}