#include <fstream>
#include <cstdio>
#include <vector>
#include <algorithm>
#define VAL 200005
#define MCH 400005

using namespace std;

struct muchie
{
    int a, b, c;
};

muchie v[MCH];

int N, M, i, j, p1, p2, fat[VAL];
int poz[VAL], sum, vfa, vfb;
int K, x[MCH], y[MCH];

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

int GetFat(int x)
{
    if (fat[x]!=x)
      fat[x]=GetFat(fat[x]);
    return fat[x];
}

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", &v[i].a, &v[i].b, &v[i].c);
    sort(v+1, v+M+1, cmp);
    for (i=1; i<=N; i++)
      fat[i]=i;
    for (i=1; i<=M; i++)
    {
        vfa=GetFat(v[i].a);
        vfb=GetFat(v[i].b);
        if (vfa!=vfb)
        {
            fat[vfa]=vfb;
            K++;
            sum+=v[i].c;
            x[K]=v[i].a;
            y[K]=v[i].b;
            if (K==N-1)
              break;
        }
    }
    printf("%d\n%d\n", sum, K);
    for (i=1; i<=K; i++)
      printf("%d %d\n", x[i], y[i]);
    return 0;
}