#include<stdio.h>
#include<stdlib.h>

#define inf 666031

typedef struct nod{
	int info;
	int cost;
	struct nod *next;
}nod;

typedef struct{
	int vf1;
	int dist;
	int vf2;
}triplet;

nod *a[200009];

void adauga(int x,nod **u,int c){
	nod *nou = (nod*)malloc(sizeof(nod));
	nod *ultim = *u;
	nou->info = x;
	nou->cost = c;
	nou->next = ultim;
	*u = nou;
}

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

void urca(int poz,triplet *h){
	int t = poz / 2;
	while(t >= 1){
		if(h[t].dist <= h[poz].dist)
			break;
		swap(&h[t].vf1,&h[poz].vf1);
		swap(&h[t].dist,&h[poz].dist);
		swap(&h[t].vf2,&h[poz].vf2);
		poz = t;
		t = poz / 2;
	}
}
	
void coboara(int poz,int n,triplet *h){
	int fs = 2 * poz,fd = 2 * poz + 1,pmin = poz;
	if(fs <= n && h[fs].dist < h[pmin].dist)
		pmin = fs;
	if(fd <= n && h[fd].dist < h[pmin].dist)
		pmin = fd;
	if(pmin != poz){
		swap(&h[pmin].vf1,&h[poz].vf1);
		swap(&h[pmin].dist,&h[poz].dist);
		swap(&h[pmin].vf2,&h[poz].vf2);
		coboara(pmin,n,h);
	}
}

void prim(int x,int n,int m){
	FILE *g;
	g = fopen("apm.out","w");
	nod *u;
	int l = 0,i;
	int cost = 0,nrm = 0;
	triplet *h = (triplet*)malloc((m + 1) * sizeof(triplet));
	triplet *aux = (triplet*)malloc((m + 1) * sizeof(triplet));
	int *marcat = (int*) malloc((n + 1) * sizeof(int));
	int *d = (int*)malloc((n + 1) * sizeof(int));
	for(i = 1;i <= n;i++)
		d[i] = inf;
	int vf = x;
	d[vf] = 0;
	marcat[vf] = 1;
	for(u = a[vf];u != NULL;u = u->next){
		h[++l] = (triplet){vf,u->cost,u->info};
		d[u->info] = u->cost;
		urca(l,h);
	}
	while(1){
		while(l != 0 && marcat[h[1].vf2] == 1){
			swap(&h[1].vf1,&h[l].vf1);
			swap(&h[1].dist,&h[l].dist);
			swap(&h[1].vf2,&h[l--].vf2);
			coboara(1,l,h);
		}
		if(l == 0)
			break;
		vf = h[1].vf2;
		d[vf] = h[1].dist;
		cost += h[1].dist;
		aux[++nrm] = h[1];
		marcat[vf] = 1;
		for(u = a[vf];u != NULL;u = u->next){
			if(u->cost >= d[u->info] || marcat[u->info] == 1)
				continue;
			h[++l] = (triplet){vf,u->cost,u->info};
			d[u->info] = u->cost;
			urca(l,h);
		}
	}
	fprintf(g,"%d\n",cost);
	fprintf(g,"%d\n",nrm);
	for(i = 1;i <= nrm;i++)
		fprintf(g,"%d %d\n",aux[i].vf1,aux[i].vf2);
	free(d);
	free(h);
	free(aux);
	fclose(g);
}
	
int main(){
	FILE *f;
	f = fopen("apm.in","r");
	int n,m,i,k1,k2,c;
	fscanf(f,"%d%d",&n,&m);
	for(i = 0;i < m;i++){
		fscanf(f,"%d%d%d",&k1,&k2,&c);
		adauga(k2,&a[k1],c);
		adauga(k1,&a[k2],c);
	}
	prim(1,n,m);
	fclose(f);
	return 0;
}