#include <cstdio>
#include <algorithm>

using namespace std;

const int nmax = 200005;

struct muchie{
              long x,y,c;
             }u[nmax],sol[nmax];

long n,m,k,i,ct,radacina_x,radacina_y,tata[nmax];

inline bool cmpf(muchie x, muchie y)
{
	return (x.c<y.c);
}

inline int root(int x)
{
	if (tata[x] == x) return x;
		tata[x] = root(tata[x]);
	return tata[x];
}

int main()
{
    freopen("apm.in","r",stdin);
    freopen("apm.out","w",stdout);
    scanf("%ld %ld", &n, &m);
    for (i=1;i<=m;++i)
        scanf("%ld %ld %ld", &u[i].x, &u[i].y, &u[i].c), tata[i]=i;
    sort(u+1, u+m+1, cmpf);
    i=1;
    while (k<n-1)
          {
			radacina_x=root(u[i].x);
			radacina_y=root(u[i].y);
			if (radacina_x!=radacina_y)
			{
               ++k;
               ct+=u[i].c;
               sol[k]=u[i];
			   tata[radacina_x]=radacina_y;
			}
            ++i;
          }
    printf("%ld\n%ld\n", ct, k);
    for (i=1;i<=k;++i)
        printf("%ld %ld\n", sol[i].x, sol[i].y);
    return 0;
}