#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, x, y, z;
    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", &x, &y, &z);
    	a[i].a=x;
    	a[i].b=y;
    	a[i].c=z;
    }
	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(findset(a[i].a), findset(a[i].b));
			if(nr==n-1)
				break;
		}
	}
	printf("%d\n%d\n", sum, n-1);
	for(int i=0;i<m;i++)
		if(viz[i]==1)
			printf("%d %d\n", a[i].a, a[i].b);
    return 0;
}