#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;
	}
};
int val[200001]; // costul muchiei minime pana la apm
int edges[200001]; // de cine a fost legat i

struct cmp
{	bool operator()(int a, int b) { return val[a] < val[b]; }
};

class heap
{	int dim;
	int A[262144];
	int pin[200009]; // poz in heap
	
	public:
		
		heap() { dim = 0; }
		
		void up_heap(int poz)
		{	while(poz != 1 && val[A[poz]] < val[A[poz / 2]])
				swap(A[poz], A[poz / 2]) , swap(pin[A[poz]], pin[A[poz / 2]]) , poz /= 2;
		}
		
		void down_heap(int poz)
		{	int son;
			do
			{	son = 0;
				
				if(2 * poz <= dim)
				{	son = 2 * poz;
					if(son + 1 <= dim && val[A[son]] > val[A[son + 1]] && val[A[son + 1]] < val[A[poz]])
						son += 1;
					if(val[A[son]] > val[A[poz]]) 
						son = 0;
				}
				
				if(son) swap(A[poz], A[son]) , swap(pin[A[poz]], pin[A[son]]) , poz = son;
			}while(son);
		}
		
		void push(int x)
		{	dim++;
			A[dim] = x; pin[x] = dim;
			up_heap(dim);
		}
		
		void pop()
		{	pin[A[1]] = 0;
			A[1] = A[dim]; 
			dim--;
			down_heap(1);
		}
		
		void update(int source, int x, int y)
		{	int poz = pin[x];
			if(val[x] < y) return;
			val[x] = y; edges[x] = source;
			up_heap(poz);
			down_heap(poz);
		}
		
		int get_min() { return A[1]; }
		
		bool find(int x)
		{	return pin[x] != 0;
		}
		
		bool empty() { return dim == 0; }
		
};

int N,M;
vector<pii>gr[200001]; //graful
bool v[200001];		   //in apm
heap h;
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.get_min(); 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))
				h.update(i , k->to, k->cost);
			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;
}