#include <bits/stdc++.h>
#pragma GCC optimize("Ofast,unroll-loops")
#pragma GCC target("sse,avx,fma,avx2,bmi,bmi2,lzcnt,popcnt")

using namespace std;

class Prim {

private:
    int n;
    vector<vector<pair<int, int>>> adj;

public:

    Prim(int _n) {
        n = _n;
        adj.resize(_n);
    }

    void insert_edge(int a, int b, int c) {
        adj[a].push_back({c, b});
        adj[b].push_back({c, a});
    }

    void solve(int start_node) {
        vector<int> dist(n, 1e9), pi(n, start_node);
        vector<bool> visited(n, false); int cost = 0;
        vector<pair<int, int>> edges; edges.reserve(n - 1);
        priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;

        visited[start_node] = true;
        for (auto p : adj[start_node])
            pq.push(p), dist[p.second] = p.first, pi[p.second] = start_node;

        while(!pq.empty()) {
            auto [c, u] = pq.top();
            pq.pop();

            if (c != dist[u])
                continue;

            visited[u] = true;
            cost += c, edges.push_back({pi[u], u});

            for (auto [w, v] : adj[u])
                if (!visited[v] && dist[v] > w) {
                    dist[v] = w;
                    pi[v] = u;
                    pq.push({dist[v], v});
                }
        }

        cout << cost << '\n' << n - 1 << '\n';
        for (auto &p : edges)
            cout << 1 + p.first << ' ' << 1 + p.second << '\n';
    }
};

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

    int n, m;
    cin >> n >> m;

    Prim solver(n);
    for (int i = 0, a, b, c; i < m; ++i) {
        cin >> a >> b >> c;
        solver.insert_edge(--a, --b, c);
    }

    solver.solve(0);
    return 0;
}