#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;
int poz[VAL], sum;
int K, x[MCH], y[MCH];
vector<int> c[VAL];
vector<int>::iterator it;

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

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++)
    {
        c[i].push_back(i);
        poz[i]=i;
    }
    for (i=1; i<=M; i++)
    {
        if (poz[v[i].a]!=poz[v[i].b])
        {
            K++;
            sum+=v[i].c;
            p1=poz[v[i].a];
            p2=poz[v[i].b];
            x[K]=v[i].a;
            y[K]=v[i].b;
            for (it=c[p2].begin(); it!=c[p2].end(); it++)
            {
                poz[*it]=p1;
                c[p1].push_back(*it);
            }
            c[p2].clear();
            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;
}