#include <stdio.h>

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

const int inf = 1000000;
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);
inline void swap(int&, int&);

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

void solve()
{
	int k = s;
	plist p;
	do
	{
		in_apm[k] = 1;
		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;
			}
		}
/*
		printf ("\n\nam reimprospatat vecinii ultimului nod introdus in apm(%d).\nheapul:", 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(1);
/*
		printf ("\n\nam scos radacina heapului (%d).\nheapul:", 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]]);
		}
*/
	}
	while (heap_size);
}

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

void move_down(int tata)
{
    int fiu;
    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[heap[tata]] <= dist[heap[fiu]])
        {
            return;
        }
        swap(heap[tata], heap[fiu]);
        swap(poz[heap[tata]], poz[heap[fiu]]);
        tata = fiu;
    }
}

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;
}

inline void swap(int& a, int &b)
{
    int t = a;
    a = b;
    b = t;
}

/*
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;
}
*/