#include <stdio.h>
#include <algorithm>
#define N_MAX 200005
#define M_MAX 400005

struct Muchie {int x; int y; int c;};

int n, m;
Muchie muchii[M_MAX];
int selected[M_MAX];
int tata[N_MAX];
int h[N_MAX];

inline void citire();
int findDad(int);
bool unire(int, int);
bool comparator(const Muchie&, const Muchie&);

int main()
{
    citire();
    std::sort(muchii+1, muchii+m+1, comparator);
    for (int i = 1; i <= n; ++i) tata[i] = i;

    int alese = 0;
    int counter = 1;
    int sum = 0;

    while (alese < n-1){
        if (unire(muchii[counter].x, muchii[counter].y)){
            selected[++alese] = counter;
            sum += muchii[counter].c;
        }
        counter++;
    }

    printf("%d\n%d\n", sum, alese);

    for (int i = 1; i <= alese; ++i){
        printf("%d %d\n", muchii[selected[i]].x, muchii[selected[i]].y);
    }

    return 0;
}

inline void citire(){
    freopen("apm.in", "r", stdin);
    freopen("apm.out", "w", stdout);

    scanf("%d%d", &n, &m);

    for (int i = 1; i <= m; ++i){
        scanf("%d%d%d", &muchii[i].x, &muchii[i].y, &muchii[i].c);
    }
}

bool comparator(const Muchie &m1, const Muchie &m2){
    return (m1.c < m2.c);
}

int findDad(int nod){
    if (tata[nod] == nod){
        return nod;
    }
    tata[nod] = findDad(tata[nod]);
    return tata[nod];
}

bool unire(int n1, int n2){
    int a = findDad(n1);
    int b = findDad(n2);

    if (a != b){
        if (h[a] < h[b]) tata[a] = b;
        else if (h[a] > h[b]) tata[b] = a;
        else {
            tata[a] = b;
            h[b]++;
        }
        return true;
    }
    return false;
}