#include <bits/stdc++.h>

using namespace std;

bool cmp(vector<int> u, vector<int> v) {
    return u[2] < v[2];
}

int main() {
    ifstream cin("apm.in");
    ofstream cout("apm.out");
    
    int n; cin >> n;
    int m; cin >> m;
    vector<vector<int>> edges;
    for (int i = 0; i < m; ++i) {
        int u, v; cin >> u >> v;
        int w; cin >> w;
        edges.push_back({u, v, w});   
    }

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

    int cost = 0;
    vector<pair<int, int>> tree;
    vector<int> cc(n + 1);
    for (int i = 1; i <= n; ++i) {
        cc[i] = i;
    }

    int k = 0;
    while (tree.size() < n - 1) {
        int u = edges[k][0];
        int v = edges[k][1];
        int w = edges[k][2];
        if (cc[u] != cc[v]) {
            tree.push_back(make_pair(u, v));
            cost += w;

            int c = cc[v];
            for (int i = 1; i <= n; ++i) {
                if (cc[i] == c) {
                    cc[i] = cc[u];
                }
            }
        }
        ++k;
    }

    cout << cost << endl;
    cout << tree.size() << endl;
    for (auto p : tree) {
        cout << p.first << " " << p.second << endl;
    }

    return 0;
}