#include <stdio.h>
#include <algorithm>
#include <vector>
#include <assert.h>
#define MAXM 400005
#define MAXN 200005
using namespace std;

struct edge {
    int node1, node2, c;
};

edge e[MAXM];
int n, m, dad[MAXN], lvl[MAXN], cost;
vector< pair<int, int> > sol;

bool Comp(edge a, edge b) {
    return a.c < b.c;
}

int root(int x) {
    int y = x, aux;

    while(dad[y]) y = dad[y];
    while(dad[x]) {
        aux = dad[x];
        dad[x] = y;
        x = aux;
    }
    return y;
}

bool unify(int x, int y) {
    if((x = root(x)) == (y = root(y))) return 0;

    if(lvl[x] < lvl[y]) dad[x] = y;
    else {
        dad[y] = x;
        if(lvl[x] == lvl[y]) ++lvl[x];
    }

    return 1;
}

int main()
{
    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", &e[i].node1, &e[i].node2, &e[i].c);
    sort(e + 1, e + m + 1, Comp);

    for(int i = 1; i <= m; i++)
        if(unify(e[i].node1, e[i].node2)) {
            cost += e[i].c;
            sol.push_back(make_pair(e[i].node1, e[i].node2));
        }

    assert(sol.size() == n - 1);

    printf("%d\n", cost);
    printf("%d\n", sol.size());
    for(auto x: sol)
        printf("%d %d\n", x.first, x.second);

    return 0;
}