#include <bits/stdc++.h>
using namespace std;

struct edges {
    int x, y, c;
} graph[400001];

int n, m, t[200001], sum;
vector<pair<int, int>> v;

int radacina(int node) {
    if (t[node] == 0) {
        return node;
    }
    return t[node] = radacina(t[node]);
}

bool cmp(edges a, edges b) {
    return a.c < b.c;
}

void kruskal() {
    for (int i = 1; i <= m; ++i) {
        int r1 = radacina(graph[i].x);
        int r2 = radacina(graph[i].y);
        if (r1 != r2) {
            t[r1] = r2;
            sum += graph[i].c;
            v.push_back({graph[i].x, graph[i].y});
        }
    }
}

int main() {
    ifstream cin("apm.in");
    ofstream cout("apm.out");
    cin >> n >> m;
    for (int i = 1; i <= m; ++i) {
        cin >> graph[i].x >> graph[i].y >> graph[i].c;
    }
    sort(graph + 1, graph + m + 1, cmp);
    kruskal();
    cout << sum << "\n" << v.size() << "\n";
    for (auto i : v) {
        cout << i.first << " " << i.second << "\n";
    }
}