#include <cstdio>

#include <algorithm>
#include <vector>

using namespace std;

#define MAXN 400100

int gr[MAXN], X[MAXN], Y[MAXN], C[MAXN];
int n, m, ans, ind[MAXN];
vector<int> vans;

int group(int i)
{
    if (gr[i] == i)
        return i;
    gr[i] = group(gr[i]);
    return gr[i];
}

void reunion(int i, int j)
{
    gr[group(i)] = group(j);
}

bool comp(int i, int j)
{
    return C[i] < C[j];
}

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\n", &X[i], &Y[i], &C[i]);
        ind[i] = i;
    }

    for (int i = 1; i <= n; ++i)
        gr[i] = i;
    sort(ind + 1, ind + m + 1, comp);
    for (int i = 1; i <= m; ++i) {
        if (group(X[ind[i]]) != group(Y[ind[i]])) {
            ans += C[ind[i]];
            reunion(X[ind[i]], Y[ind[i]]);
            vans.push_back(ind[i]);
        }
    }
    printf("%d\n", ans);
    printf("%d\n", n - 1);
    for (int i = 0; i < n - 1; ++i)
        printf("%d %d\n", Y[vans[i]], X[vans[i]]);
    
    return 0;
}