#include <bits/stdc++.h>

using namespace std;

ifstream fin("apm.in");
ofstream fout("apm.out");

const int MAX_N = 200000;

struct Edge {
    int c, u, v;
};

int n, m;
int tata[MAX_N + 5], cnt[MAX_N + 5];

vector<Edge> edges;
vector<pair<int, int> > ans;

int sum;

inline bool cmp(const Edge &a, const Edge &b) {
    return a.c < b.c;
}

int root(int x) {
    if (tata[x] == x)
        return x;
    return tata[x] = root(tata[x]);
}

void join(int x, int y){
    x = root(x);
    y = root(y);

    if(cnt[x] > cnt[y])
        swap(x, y);

    cnt[y] += cnt[x];
    tata[x] =y;
}

int main() {
    int n, m;
    fin >> n >> m;
    for (int i = 1; i <= m; i++) {
        int a, b, c;
        fin >> a >> b >> c;
        edges.push_back({c, a, b});
    }

    sort(edges.begin(), edges.end(), cmp);

    for (int i = 1; i <= n; i++) {
        tata[i] = i;
        cnt[i] = 1;
    }

    for (int i = 0; i < m; i++) {
        int a = edges[i].u;
        int b = edges[i].v;
        int c = edges[i].c;

        if (root(a) == root(b))
            continue;

        join(a, b);
        sum += c;
        ans.push_back({a, b});
    }

    fout << sum << '\n' << ans.size() << '\n';
    for (auto i : ans)
        fout << i.first << ' ' << i.second << '\n';
    return 0;
}