#include <bits/stdc++.h>

#define inf (1 << 30)

std::pair<int, std::vector<int>> PrimMST(std::vector<std::vector<std::pair<int, int>>>& Graph) {
    std::vector<bool> visited(Graph.size(), false);
    std::vector<int> parents(Graph.size(), -1);
    std::priority_queue<std::pair<int, int>, std::vector<std::pair<int, int>>, std::greater<std::pair<int, int>>> Queue;
    parents[0] = 0;
    Queue.push({0, 0});
    int cost = 0;
    while (!Queue.empty()) {
        int u = Queue.top().second;
        int curr_cost = Queue.top().first;
        Queue.pop();
        if (visited[u]) continue;
        visited[u] = true;
        cost += curr_cost;
        for (auto& neighbor : Graph[u]) {
            int v = neighbor.first;
            int c = neighbor.second;
            if (!visited[v]) {
                Queue.push({c, v});
                parents[v] = u;
            }
        }
    }
    return {cost, parents};
}

int main() {
    assert(freopen("apm.in", "r", stdin));
    int V, E;
    assert(scanf("%d %d ", &V, &E) == 2);
    std::vector<std::vector<std::pair<int, int>>> Graph(V);
    for (int i = 0; i < E; ++i) {
        int x, y, w;
        assert(scanf("%d %d %d ", &x, &y, &w) == 3);
        Graph[x - 1].push_back(std::make_pair(y - 1, w));
        Graph[y - 1].push_back(std::make_pair(x - 1, w));
    }
    fclose(stdin);
    auto res = PrimMST(Graph);
    assert(freopen("apm.out", "w", stdout));
    printf("%d\n%d\n", res.first, res.second.size() - 1);
    for (size_t i = 1; i < res.second.size(); ++i) {
        printf("%d %d\n", i + 1, res.second[i] + 1);
    }
    fclose(stdout);
    return 0;
}