#include <algorithm>
#include <iostream>
#include <vector>

#define NMAX 400005

using namespace std;

typedef pair<int, int> pii;

struct muchie {
    int x, y, cost;
} a[NMAX];

int n, m, t[NMAX];
vector<pii> mans;

int findRadac(int x) {
    int radac = x;
    while(radac != t[radac]) radac = t[radac];
    while(x != t[x]) {
        int crt = t[x];
        t[x] = radac;
        x = crt;
    }
    return radac;
}

int main()
{
    freopen("apm.in", "r", stdin);
    freopen("apm.out", "w", stdout);
    scanf("%d%d", &n, &m);
    for(int i = 1; i <= n; ++i)
        t[i] = i;
    for(int i = 1; i <= m; ++i)
        scanf("%d%d%d", &a[i].x, &a[i].y, &a[i].cost);
    sort(a + 1, a + m + 1, [](const muchie X, const muchie Y) {
         return X.cost < Y.cost;
    });
    int ans = 0;
    for(int i = 1; i <= m; ++i) {
        int tx = findRadac(a[i].x), ty = findRadac(a[i].y);
        if(tx != ty) {
            ans += a[i].cost;
            t[tx] = ty;
            mans.push_back({a[i].x, a[i].y});
        }
    }
    printf("%d\n%d\n", ans, n - 1);
    for(const auto &el : mans)
        printf("%d %d\n", el.first, el.second);
    return 0;
}