// MST (Minimum Spanning Tree)- Prim's Algorithm
#include <cstdio>
#include <queue>
#include <string>
#define N 200001
#define L (i<<1)
#define R (L|1)
#define T (i>>1)
#define oo 0x3f3f3f3f //infinity
#define dim 8192
char ax[dim];
int pz;

inline void cit(int &x)
{
	x = 0;
	while((ax[pz] < '0' || ax[pz] > '9') && ax[pz] != '-')
		if(++pz == dim) fread(ax,1,dim,stdin),pz = 0;
	
	bool neg = 0;
	if(ax[pz] == '-')
	{
		neg = 1;
		if(++pz == dim) fread(ax,1,dim,stdin),pz = 0;
	}
	
	while(ax[pz] >= '0' && ax[pz] <= '9')
	{
		x = x + ax[pz] - '0';
		if(++pz == dim) fread(ax,1,dim,stdin),pz = 0;
	}
	
	if(neg) x = -x;
}

using namespace std;

int n;// number of nodes
int m;// number of edges

struct nod
{
	int x; // adjancent node
	int c; // cost
	nod *next;
};

nod * a[N]; // adjacency list
int d[N];  // minimum value of an edge of node i
int t[N]; // father

int H[N]; //heap
int poz[N]; // poz[H[i]] = i
int nh; // number of elements in heap

int rez[N][2];
int ns;

inline void add(int i, int j, int c)
{
	nod *p = new nod;
	p->x = j;
	p->c = c;
	p->next = a[i];
	a[i] = p;
}

inline void swap(int i, int j)
{
	int t = H[i];
	H[i] = H[j];
	H[j] = t;
	poz[H[i]] = i;
	poz[H[j]] = j;
}

inline void upheap(int i)
{
	if(i <= 1) return ;
	if(d[H[i]] < d[H[T]]) swap(i, T), upheap(T);
}

inline void downheap(int i)
{
	int mn = i;
	
	if(L <= nh)
		if(d[H[L]] < d[H[mn]]) mn = L;
	if(R <= nh)
		if(d[H[R]] < d[H[mn]]) mn = R;
	
	if(i != mn) swap(i, mn), downheap(mn);
}

void read()
{
	freopen("apm.in","r",stdin);
	cit(n); cit(m);
	int p, q,c;
	
	while(m--)
	{
		
		cit(p); cit(q); cit(c);
		add(p,q,c);
		add(q,p,c);
	}
}


void Prim()
{
	int i, j;
	int sol = 0;
	
	bool used[N];
	
	for(i = 1; i <= n; ++i)
		d[i] = oo, t[i] = 0, used[i] = 0,H[i] = i, poz[i] = i;
	
	d[1] = 0;
	
	nh = n;
	
	for(i = n/2; i ; --i)
		downheap(i);
	
	while(nh)
	{
		int u = H[1];
		swap(1, nh--);
		downheap(1);
		
		sol += d[u];
		used[u] = 1;
		
		if(t[u]) rez[++ns][0] = u, rez[ns][1] = t[u];
		
		for(nod *it = a[u]; it ; it = it->next)
			if(!used[it->x] && it->c < d[it->x])
			{
				t[it->x] = u;
				d[it->x] = it->c;
				upheap(poz[it->x]);
			}
	}
	
	freopen("apm.out","w",stdout);
	
	printf("%d\n", sol);
	printf("%d\n", ns);
	for(i = 1; i <= ns; ++i)
		printf("%d %d\n", rez[i][0], rez[i][1]);
	

	
}

int main()
{
	read();
	Prim();

	return 0;
}