#include <cstdio>
#include <algorithm>

using namespace std;

struct nod
{
	int a, b;
	int c;
};
bool comp(nod a, nod b)
{
	return a.c<b.c;
}
nod a[400001];
int t[200001], h[200001];
bool viz[400001];

void unionset(int x, int y)
{
	if(h[x]==h[y])
	{
		h[x]++;
		t[y]=x;
	}
	else if(h[x]<h[y])
		t[x]=y;
	else t[y]=x;
}
int findset(int x)
{
	while(t[x]!=x)
		x=t[x];
	return x;
}

int main()
{
    freopen("apm.in", "r", stdin);
    freopen("apm.out", "w", stdout);
    int n, m, sum=0, nr=0;
    scanf("%d%d", &n, &m);
    for(int i=0;i<n;i++)
		t[i]=i;
    for(int i=0;i<m;i++)
		scanf("%d%d%d", &a[i].a, &a[i].b, &a[i].c);
	sort(a, a+m, comp);
	for(int i=0;i<m;i++)
	{
		if(findset(a[i].a)!=findset(a[i].b))
		{
			nr++;
			viz[i]=1;
			sum+=a[i].c;
			unionset(t[a[i].a], t[a[i].b]);
			if(nr==n-1)
				break;
		}
	}
	printf("%d\n%d\n", sum, n-1);
	for(int i=0;i<n-1;i++)
		printf("%d %d\n", a[i].a, a[i].b);
    return 0;
}