#include <bits/stdc++.h>
using namespace std;
ifstream fin("apm.in");
ofstream fout("apm.out");
int const N = 4e5 + 4;
vector<int> height(N), group(N);
vector<pair<int, int>> ans;
set<pair<int, pair<int, int>>> edges;
int n, m;

int find_root(int x) {
    int node = x;
    while (group[node] != node) {
        node = group[node];
    }
    while (group[x] != x) {
        int aux = group[x];
        group[x] = node;
        x = aux;
    }
    return node;
}

void unite(int x, int y) {
    if (height[x] > height[y]) {
        group[y] = x;
    } else {
        group[x] = y;
    }
    if (height[x] == height[y]) {
        height[y]++;
    }
}

int main() {
    ios::sync_with_stdio(0), cin.tie(0);
    fin >> n >> m;
    for (int i = 1; i <= n; ++i) {
        height[i] = 1;
        group[i] = i;
    }
    for (int i = 1; i <= m; ++i) {
        int cost, x, y;
        fin >> x >> y >> cost;
        edges.insert({cost, {x, y}});
    }
    int total_cost = 0;
    for (auto [cost, nr] : edges) {
        int x = nr.first, y = nr.second;
        if (find_root(x) != find_root(y)) {
            total_cost += cost;
            ans.push_back({x, y});
            unite(find_root(x), find_root(y));
        }
    }
    fout << total_cost << '\n' << n - 1 << '\n';
    for (auto [x, y] : ans) {
        fout << x << ' ' << y << '\n';
    }
    return 0;
}