#include <vector>
#include <fstream>
#include <cstdlib>

using namespace std;
typedef pair<int, int> pr;

const int oo=1<<29;
const int N_MAX=200011;

vector<pr> G[N_MAX];
int lHeap;
int d[N_MAX], H[N_MAX], P[N_MAX], apm[N_MAX];
vector<pr>::const_iterator it, iend;

inline void _swap(int& x, int& y) {int aux=x; x=y; y=aux;}
void DownHeap(int k)
{
	for(int son=k<<1; son <= lHeap; k=son, son<<=1)
	{
		if(son < lHeap && d[H[son]] > d[H[son+1]])
			++son;
		if(d[H[k]] <= d[H[son]])
			return;
		_swap(H[k], H[son]);
		P[H[k]]=k;
		P[H[son]]=son;
	}
}
void UpHeap(int k)
{
	for(int key=d[H[k]], f=k>>1; k > 1 && key < d[H[f]]; k=f, f>>=1)
	{
		_swap(H[k], H[f]);
		P[H[k]]=k;
		P[H[f]]=f;
	}
}
inline void push(int x)
{
	H[++lHeap]=x;
	P[x]=lHeap;
	UpHeap(lHeap);
}
inline int pop()
{
	int r=H[1];
	P[H[1]]=-1;
	H[1]=H[lHeap];
	P[H[1]]=1;
	--lHeap;
	DownHeap(1);
	
	return r;
}

int main()
{
	int N, M, i, x, y, c, s;
	ifstream in("apm.in");
	ofstream out("apm.out");
	
	for(in>>N>>M; M; --M)
	{
		in>>x>>y>>c;
		G[x].push_back(pr(y,c));
		G[y].push_back(pr(x,c));
	}
	fill(d, d+N+1, oo);
	d[1]=0;
	for(s=0, push(1); lHeap; )
	{
		x=pop();
		s+=d[x];
		for(it=G[x].begin(), iend=G[x].end(); it < iend; ++it)
		{
			if(-1 == P[it->first])
				continue;
			if(oo == d[it->first])
			{
				d[it->first]=it->second;
				apm[it->first]=x;
				push(it->first);
			}
			else if(d[it->first] > it->second)
				{	
					d[it->first]=it->second;
					apm[it->first]=x;
					UpHeap(P[it->first]);
				}
		}
	}
	out<<s<<'\n'<<(N-1)<<'\n';
	for(i=2; i <= N; ++i)
		out<<i<<' '<<apm[i]<<'\n';
	
	return EXIT_SUCCESS;
}