#include <vector>
#include <algorithm>
#include <cstdio>
using namespace std;

#define maxn 200020
#define inf 2000000000
#define in "apm.in"
#define out "apm.out"
#define pb push_back

int h[maxn],cost[maxn],p[maxn],cnt;
vector<int> g[maxn],c[maxn];
int t[maxn],N,M;
bool inApm[maxn];

void update(int poz)
{
	int tata = poz/2;
	while(tata && cost[h[poz]] < cost[h[tata]])
	{
			swap(h[poz],h[tata]);
			swap(p[h[poz]],p[h[tata]]);
			tata = poz; poz >>= 1;
	}
}

void pop()
{
	p[h[1]] = 0;
	h[1] = h[cnt--];
	if(cnt > 0)
		p[h[1]] = 1;
	int tata = 1,fiu = 2;
	while(fiu <= cnt)
	{
		if(cost[h[fiu]] < cost[h[fiu + 1]]) fiu++;
		if(cost[h[fiu]] < cost[h[tata]])
		{
			swap(h[fiu],h[tata]);
			swap(p[h[fiu]],p[h[tata]]);
			tata = fiu;
			fiu<<=1;
		}
		else
			fiu = cnt + 1;
	}
}

void push(int nod)
{
	h[++cnt] = nod;
	p[h[cnt]] = cnt;
	int tata = cnt/2,fiu = cnt;
	while(tata && cost[h[fiu]] < cost[h[tata]])
	{
		swap(h[fiu],h[tata]);
		swap(p[h[fiu]],p[h[tata]]);
		fiu = tata;
		tata >>= 1;
	}
}

int main()
{
	freopen (in,"r",stdin);
	freopen (out,"w",stdout);
	
	scanf("%d %d",&N,&M);
	int i,x,y,z,ans = 0;
	
	for(i = 1; i <= M; i++)
	{
		scanf("%d %d %d",&x,&y,&z);
		g[x].pb(y);
		g[y].pb(x);
		c[x].pb(z);
		c[y].pb(z);
	}
	
	for(i = 1; i <= N; i++)
		cost[i] = inf;
	cost[1] = t[1] = 0;
	
	push(1);
	
	for(i = 1; i <= N; i++)
	{
		x = h[1];
		inApm[x] = 1;
		ans += cost[x];
		pop();
		for(y = 0; y < g[x].size(); y++)
		{
			z = g[x][y];
			if(c[x][y] < cost[z])
				if(!inApm[z])
				if(p[z])
				{
					t[z] = x;
					cost[z] = c[x][y];
					update(p[z]);
				}
				else
				{
					t[z] = x;
					cost[z] = c[x][y];
					push(z);
				}
		}
	}
	
	printf("%d\n%d\n",ans,N - 1);
	
	for(i = 1; i <= N; i++)
		if(t[i])
			printf("%d %d\n",i,t[i]);
	return 0;
	
}