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

using namespace std;

const int NMAX = 2e5 + 5;
const int MMAX = 4e5 + 5;
const char nl = '\n';

struct edge{
    int u, v, w;
};

bool cmp(edge &a, edge &b) {
    return a.w < b.w;
}

edge edg[MMAX];
int father[NMAX], rankk[NMAX];
vector<edge> tree;

int find(int node) {
    if(father[node] == node) {
        return node;
    }
    return father[node] = find(father[node]);
}

bool unite(int x, int y) {
    x = find(x);
    y = find(y);

    if(x == y) {
        return false;
    }
    if(rankk[x] < rankk[y]) {
        father[x] = y;
    } else if(rankk[x] > rankk[y]) {
        father[y] = x;
    } else {
        father[y] = x;
        rankk[x]++;
    }

    return true;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    freopen("apm.in", "r", stdin);
    freopen("apm.out", "w", stdout);

    int n, m;
    cin >> n >> m;
    for(int i = 1; i <= m; ++i) {
        cin >> edg[i].u >> edg[i].v >> edg[i].w;
    }

    sort(edg + 1, edg + m + 1, cmp);

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

    int sum = 0;
    for(int i = 1; i <= m; ++i) {
        if(unite(edg[i].u, edg[i].v)) {
            tree.push_back({edg[i].u, edg[i].v, edg[i].w});
            sum += edg[i].w;
        }
    }

    cout << sum << nl << tree.size() << nl;
    for(auto x: tree) {
        cout << x.v << ' ' << x.u << nl;
    }
    return 0;
}