#include <bits/stdc++.h>

std::ifstream in("apm.in");
std::ofstream out("apm.out");

const int N = 1000;
const int Inf2 = 1 << 30;

struct PartEdge {
    int to, c;
};

int n;
std::vector<PartEdge> g[N];
int d[N], pred[N];
bool vis[N];

std::pair<int, std::vector<std::pair<int, int>>> apn() {
    for (int i = 2; i <= n; ++i) {
        d[i] = Inf2;
    }
    int rs = 0;
    std::vector<std::pair<int, int>> tree;
    std::priority_queue<std::pair<int, int>> h;
    h.push({0, 1});
    while (!h.empty()) {
        int u = h.top().second;
        h.pop();
        if (vis[u]) {
            continue;
        }
        vis[u] = true;
        if (pred[u] != 0) {
            tree.push_back({u, pred[u]});
        }
        rs += d[u];
        for (auto e : g[u]) {
            if (!vis[e.to] && e.c < d[e.to]) {
                d[e.to] = e.c;
                pred[e.to] = u;
                h.push({-e.c, e.to});
            }
        }
    }
    return {rs, tree};
}

int main() {
    int m;
    in >> n >> m;
    for (int i = 0; i < m; ++i) {
        int u, v, c;
        in >> u >> v >> c;
        g[u].push_back({v, c});
        g[v].push_back({u, c});
    }
    auto res = apn();
    out << res.first << '\n' << res.second.size() << '\n';
    for (auto e : res.second) {
        out << e.first << ' ' << e.second << '\n';
    }
}