#include <bits/stdc++.h>

#define inf (1 << 30)

std::vector<int> PrimMST(std::vector<std::vector<std::pair<int, int>>>& Graph) {
    std::vector<int> keys(Graph.size(), inf);
    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;
    std::vector<std::pair<int, int>> edges;
    keys[0] = 0;
    parents[0] = 0;
    Queue.push({0, 0});
    while (!Queue.empty()) {
        int node = Queue.top().second;
        Queue.pop();
        visited[node] = true;
        for (auto& neighbor : Graph[node]) {
            if (!visited[neighbor.first] && keys[neighbor.first] > neighbor.second) {
                keys[neighbor.first] = neighbor.second;
                Queue.push({keys[neighbor.first], neighbor.first});
                parents[neighbor.first] = node;
            }
        }
    }
    return 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);
    int cost = 0;
    for (size_t i = 1; i < res.size(); ++i) {
        for (auto& p : Graph[i]) {
            if (p.first == res[i]) {
                cost += p.second;
                break;
            }
        }
    }
    assert(freopen("apm.out", "w", stdout));
    printf("%d\n%d\n", cost, res.size() - 1);
    for (size_t i = 1; i < res.size(); ++i) {
        printf("%d %d\n", i + 1, res[i] + 1);
    }
    fclose(stdout);
    return 0;
}