#include <bits/stdc++.h>

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

void prim() {

    min_e[1].first = 0;
    q.push({0, 1});

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

        if (selected[v.second]) {
            continue;
        }

        selected[v.second] = 1;
        cmin += v.first;

        if (min_e[v.second].second != -1) {
            ans.push_back({v.second, min_e[v.second].second});
        }

        for (auto it : adj[v.second]) {
            if (!selected[it.second] && it.first < min_e[it.second].first) {
                min_e[it.second] = {it.first, v.second};
                q.push({it.first, it.second});
            }
        }
    }
}

int main()
{
    in>>n>>m;
    for (int i = 0; i <= n; i++) {
        min_e.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();

    out<<cmin<<'\n';
    out<<n - 1<<'\n';

    for (auto it : ans) {
        out<<it.first<<" "<<it.second<<'\n';
    }
    return 0;
}