#include <bits/stdc++.h>

using namespace std;
ifstream in("apm.in");
ofstream out("apm.out");
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> q;
int n, m, x, y, c;
int cmin = 0;
vector<pair<int, int>> adj[200005];
vector<pair<int, int>> ans;
bool vis[200005];
vector<pair<int, int>> min_edge;

void prim(int nod) {
    q.push({0, nod});
    min_edge[nod].first = 0;

    while (!q.empty()) {
        pair<int, int> node = q.top();
        q.pop();

        if (vis[node.second] == 1)
            continue;
        vis[node.second] = 1;

        cmin += node.first;
        if (min_edge[node.second].second != -1) {
            ans.push_back({node.second, min_edge[node.second].second});
        }

        for (auto it : adj[node.second]) {
            if (!vis[it.second] && it.first < min_edge[it.second].first) {
                min_edge[it.second].first = it.first;
                min_edge[it.second].second = node.second;
                q.push({it.first, it.second});
            }
        }
    }
}

int main()
{
    in >> n >> m;
    for (int i = 0; i <= n; i++) {
        min_edge.push_back({1e9, -1});
    }

    for (int i = 1; i <= m; i++) {
        in >> x >> y >> c;
        adj[x].push_back({c, y});
        adj[y].push_back({c, x});
    }

    prim(1);

    out << cmin << '\n' << n - 1 << '\n';
    for (auto it : ans)
        out << it.first << " " << it.second << '\n';

    return 0;
}