#include <stdio.h>

typedef struct list
{
	int nod, val;
	list *next;
} *plist;

const int inf = 10000;
int n, m, s, heap_size = 0, cost_total = 0;
int *heap, *in_apm, *dist, *poz, *t;
plist *vecini;

void read();
void solve();
void write();
void move_up(int);
void move_down(int);
inline void add(int, int, int);

int main()
{
	read();
	solve();
	write();
	return 0;
}

void solve()
{
	int k = s;
	plist p;
	do
	{
		in_apm[k] = 1;
		printf ("\n\nla cost_total adaug dist[k]: %d += %d\nheapul:", cost_total, dist[k]);
		for (p = vecini[k]; p; p = p->next)					//adaug(actualizez) toti vecinii lui k
		{
			if (!in_apm[p->nod] && dist[p->nod] > p->val)
			{
				if (dist[p->nod] == inf)
				{
					heap[++heap_size] = p->nod;
					poz[p->nod] = heap_size;
				}
				dist[p->nod] = p->val;
				move_up(poz[p->nod]);
				t[p->nod] = k;
			}
		}
		for (int i = 1; i <= heap_size; ++i)
		{
			printf (" %d", heap[i]);
		}
		printf ("\ndistanta:");
		for (int i = 1; i <= heap_size; ++i)
		{
			printf (" %d", dist[heap[i]]);
		}
		k = heap[1];										//scot radacina heapului
		cost_total += dist[k];
		heap[1] = heap[heap_size];
		--heap_size;
		move_down(heap[1]);
	}
	while (heap_size);
}

void move_up(int fiu)
{
	int tata, h_fiu = heap[fiu];
	for (tata = fiu / 2; tata >= 1 && dist[heap[tata]] > dist[h_fiu]; tata = tata / 2)
	{
		heap[fiu] = heap[tata];
		poz[heap[fiu]] = fiu;
		fiu = tata;
	}
	heap[fiu] = h_fiu;
	poz[heap[fiu]] = fiu;
}

void move_down(int tata)
{
	int fiu, h_tata = heap[tata];
	for (fiu = tata * 2; fiu <= heap_size; fiu = fiu * 2)
	{
		if (fiu < heap_size)
		{
			if (dist[heap[fiu+1]] < dist[heap[fiu]])
			{
				++fiu;
			}
		}
		if (dist[h_tata] >= dist[fiu])
		{
			break;
		}
		heap[fiu/2] = heap[fiu];
		poz[heap[fiu/2]] = fiu / 2;
		tata = fiu;
	}
	heap[tata] = h_tata;
	poz[heap[tata]] = tata;
}

void write()
{
	int i;
	FILE *fout = fopen ("apm.out", "w");
	fprintf (fout, "%d\n%d\n", cost_total, n - 1);
	for (i = 1; i <= n; ++i)
	{
		if (t[i])
		{
			fprintf (fout, "%d %d\n", t[i], i);
		}
	}
	fclose (fout);
}

void read()
{
	int i, x, y, z, minx, miny, minz;
	FILE *fin = fopen ("apm.in", "r");
	fscanf (fin, "%d%d", &n, &m);
	vecini = new plist[n+1];
	for (i = 1; i <= n; ++i)
	{
		vecini[i] = 0;
	}
	fscanf (fin, "%d%d%d", &x, &y, &z);
	minx = x;
	miny = y;
	minz = z;
	add(x, y, z);
	for (i = 2; i <= m; ++i)
	{
		fscanf (fin, "%d%d%d", &x, &y, &z);
		if (minz > z)
		{
			minx = x;
			miny = y;
			minz = z;
		}
		add(x, y, z);
	}
	fclose (fin);
	heap = new int[n+1];
	in_apm = new int[n+1];
	dist = new int[n+1];
	poz = new int[n+1];
	t = new int[n+1];
	for (i = 1; i <= n; ++i)
	{
		in_apm[i] = 0;
		dist[i] = inf;
		t[i] = 0;
	}
	s = minx;
	dist[s] = 0;
}

inline void add(int x, int y, int z)
{
	plist p = new list;
	p->nod = y;
	p->val = z;
	p->next = vecini[x];
	vecini[x] = p;
	p = new list;
	p->nod = x;
	p->val = z;
	p->next = vecini[y];
	vecini[y] = p;
}