#include<stdio.h>
#include<vector>
using namespace std;

struct heap{int a,b,c;}h[ 400010 ],Y;
vector<int> v[ 200010 ],cost[ 200010 ];
int i,j,k,l,m,n,sol,a,b,c,N,t[ 200010 ];
int viz[ 200010 ];

void update(){
int x = k;
heap aux;
while(h[x].c < h[x>>1].c && x > 1)
	{aux = h[x];
	h[x] = h[x>>1];
	h[x>>1] = aux;
	x = x>>1;
	}
 
}

void del(){
int f1=2,f2=3,nod = 1;;
h[1] = h[k];
h[k].a = h[k].b = h[k].c = 0;
k--;
heap aux;
while((h[nod].c > h[f1].c && f1 <= k) || (h[nod].c > h[f2].c && f2 <= k))
	{if(f2 < k)
		{if(h[f1].c < h[f2].c)
			{aux = h[nod];
			h[nod] = h[f1];
			h[f1] = aux;
			nod = f1;
			f1 = 2*nod;
			f2 = 2*nod+1;
			}
		else
			{aux = h[nod];
			h[nod] = h[f2];
			h[f2] = aux;
			nod = f2;
			f1 = 2*nod;
			f2 = 2*nod+1;
			}
		}
	else
	if(h[nod].c > h[f1].c)
		{aux = h[nod];
			h[nod] = h[f1];
			h[f1] = aux;
			nod = f1;
			f1 = 2*nod;
			f2 = 2*nod+1;
		}
	}

}

int main(){
freopen("apm.in","r",stdin);
freopen("apm.out","w",stdout);

scanf("%d %d",&n,&m);

for(i = 1; i <= m; i++)
	{scanf("%d %d %d",&a,&b,&c);
	v[a].push_back(b);
	cost[a].push_back(c);
	v[b].push_back(a);
	cost[b].push_back(c);
	}
	
N  = v[1].size();
viz[1] = 1;
for(i = 0 ; i < N ; i++)
	{
	b = v[1][i];
	c = cost[1][i];
	k++;
	h[k].b = 1;
	h[k].a = b;
	h[k].c = c;
	update();
	}
while(k){Y = h[1];
del();
if(!viz[Y.a])
	{sol += Y.c;
	t[Y.a] = Y.b;
	viz[Y.a] = 1;
	N = v[Y.a].size();
	for(i = 0 ; i < N ; i++)
		{if(!viz[v[Y.a][i]])
			{k++;
			h[k].a = v[Y.a][i];
			h[k].c = cost[Y.a][i];
			h[k].b = Y.a;
			update();
			}
		}
	}
	

}
printf("%d\n%d\n",sol,n-1);

for(i = 1 ; i <= n ; i++)
	if(t[i])
		printf("%d %d\n",i,t[i]);
	

return 0;}