#include <fstream>
#include <vector>
#define inf (1<<30)
using namespace std;
ifstream f("apm.in");
ofstream g("apm.out");
vector < pair < int, int > > vecini[200000],sol;
vector < pair < int, int > > heap;
int dist[200000],poz[200000];
int n,m,lh=1,len;
void percolate(int k)
{
	if(dist[heap[k/2].first]>dist[heap[k].first] && k/2>1)
	{
		poz[heap[k].first]=k/2;
		poz[heap[k/2].first]=k;
		swap(heap[k],heap[k/2]);
		percolate(k/2);
	}
}
void sift(int k)
{
	int son=0;
	if(2*k<=lh) son=2*k;
	if(2*k+1<=lh && dist[heap[son+1].first]<dist[heap[son].first]) son=son+1;
	if(dist[heap[son].first]<dist[heap[k].first] && son) 
	{
		poz[heap[son].first]=k;
		poz[heap[k].first]=son;
		swap(heap[k],heap[son]);
		sift(son);
	}
}
void adaugare(int a,int x)
{
	heap.push_back(make_pair(a,x)); lh++;
	poz[a]=lh;
	percolate(lh);
}
int main()
{
	f>>n>>m;
	int x,y,c,i;
	for(i=0;i<m;i++)
	{
		f>>x>>y>>c;
		vecini[x].push_back(make_pair(y,c));
		vecini[y].push_back(make_pair(x,c));
	}
	for(i=2;i<=n;i++) dist[i]=inf;
	poz[1]=1;
	heap.push_back(make_pair(0,0));
	heap.push_back(make_pair(1,0));
	while(lh)
	{
		x=heap[1].first; len+=dist[x]; 
		if(x!=1) sol.push_back(make_pair(x,heap[1].second));
		dist[x]=-1001;
		for(i=0;i<vecini[x].size();i++)
		{
			if(dist[vecini[x][i].first]!=-1001)
				if(dist[vecini[x][i].first]==inf)
				{
					dist[vecini[x][i].first]=vecini[x][i].second;
					adaugare(vecini[x][i].first,x);
				}
				else if(dist[vecini[x][i].first] > vecini[x][i].second)
				{
					dist[vecini[x][i].first]=vecini[x][i].second;
					percolate(poz[vecini[x][i].first]);
					heap[poz[vecini[x][i].first]].second=x;
				}
		}
		swap(heap[1],heap[lh]); poz[heap[1].first]=1;
		lh--;
		heap.pop_back();
		if(lh) sift(1);
	}
	g<<len<<'\n'<<sol.size()<<'\n';
	for(i=0;i<sol.size();i++)
		g<<sol[i].first<<' '<<sol[i].second<<'\n';
}