#include <bits/stdc++.h>

using namespace std;

int main() {
    int n; cin >> n;
    int m; cin >> m;
    vector<vector<pair<int, int>>> adj(n + 1);
    for (int i = 0; i < m; ++i) {
        int u, v; cin >> u >> v;
        int w; cin >> w;
        adj[u].push_back(make_pair(v, w));
        adj[v].push_back(make_pair(u, w));
    }

    int cost = 0;
    vector<pair<int, int>> tree;
    vector<bool> added(n + 1, false);
    added[1] = true;
    for (int i = 1; i < n; ++i) {
        int min_cost = INT_MAX;
        int v1, v2;
        for (int u = 1; u <= n; ++u) {
            if (added[u]) {
                for (auto p : adj[u]) {
                    int v = p.first;
                    int w = p.second;
                    if (!added[v] and w < min_cost) {
                        min_cost = w;
                        v1 = u;
                        v2 = v;
                    }
                }
            }
        }
        // cout << v1 << " " << v2 << " " << cost << endl;
        added[v2] = true;
        cost += min_cost;
        tree.push_back(make_pair(v1, v2));
    }

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

    return 0;
}