#include<fstream>
#include<iostream>
#include<vector>
#include<set>
using namespace std;

#define mp make_pair

ifstream f("apm.in");
ofstream g("apm.out");

struct pii
{	int to,cost;
	pii() {}
	pii(int v1,int v2)
	{	to = v1; cost = v2;
	}
};

class heap
{	int dim;
	int *A;
	int *val;	//val = values of nodes for comparison
	int *pin;		//position in heap
	
	public:
		
		heap(){}
		heap(int d, int values[])
		{	
			A = new int[d];
			pin = new int[d];
			val = values;
			dim = 0;
		}
		
		void up_heap(int pos)
		{	
			while(pos != 1 && val[A[pos]] < val[A[pos / 2]])
			{	swap(pin[A[pos]], pin[A[pos / 2]]);
				swap(A[pos], A[pos / 2]);
				pos /= 2;
			}
		}
		
		void down_heap(int pos)
		{	int son = 0;
			do
			{	son = 0;
				
				if(2 * pos <= dim && val[A[pos]] > val[A[2 * pos]])
					son = 2 * pos;
				
				if(2 * pos + 1 <= dim && val[A[pos]] > val[A[2 * pos + 1]] && val[A[2 * pos + 1]] < val[A[2 * pos]])
					son = 2 * pos + 1;
				
				if(son)
				{	swap(pin[A[pos]], pin[A[son]]);
					swap(A[pos], A[son]);
					pos = son;
				}
			}while(son);
		}
		
		void push(int node)
		{	 
			A[++dim] = node;
			pin[node] = dim;
			up_heap(dim);
		}
		
		void pop()
		{	
			pin[A[1]] = -1;
			pin[A[dim]] = 1;
			swap(A[1], A[dim]);
			dim--;
			down_heap(1);
		}
		
		int find(int node)
		{	if(pin[node] == -1) return 0;
			else return pin[node];
		}
		
		void update(int node)
		{	int pos = find(node);
			up_heap(pos);
			down_heap(pos);
		}
		
		int root()
		{	return A[1];
		}
		
		bool empty()
		{	return dim == 0;
		}
};

int N,M;
vector<pii>gr[200001]; //graful
bool v[200001];		   //in apm
int val[200001]; // costul muchiei minime pana la apm
int edges[200001]; // de cine a fost legat i
heap h(200001, val);

typedef vector<pii>::iterator it;

int main()
{	int i,j,x,y;
	int S = 0;
	
	f>>N>>M;
	for(i = 1; i <= M; i++)
	{	f>>x>>y>>j;
		gr[x].push_back(pii(y,j));
		gr[y].push_back(pii(x,j));
	}
	
	val[1] = 0; h.push(1); v[1] = 1; edges[1] = 0;
	
	while(!h.empty())
	{	i = h.root(); S += val[i]; v[i] = 1;
		h.pop();
		
		for(it k = gr[i].begin(); k != gr[i].end(); k++)
		{	if(v[k->to]) continue;
		
			if(h.find(k->to))
			{	if(val[k->to] > k->cost)
				{	val[k->to] = k->cost;
					edges[k->to] = i;
					h.update(k->to);
				}
			}
			else val[k->to] = k->cost , h.push(k->to) , edges[k->to] = i;
		}
		
	}
	
	g<<S<<'\n';
	g<<N - 1<<'\n';
	for(i = 2; i <= N; i++) g<<i<<" "<<edges[i]<<'\n';
	
	f.close();
	g.close();
	return 0;
}