#include <bits/stdc++.h>

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

typedef std::pair<int,int> PII;

int main () {

    int n;
    input >> n;
    std::vector<std::vector<PII>> graph(n+1);
    //first - cost
    //second - id

    int m;
    input >> m;
    for(int i = 1; i <= m; i++){
        int x, y, c;
        input >> x >> y >> c;
        graph[x].push_back({c, y});
        graph[y].push_back({c, x});
    }

    std::priority_queue<PII, std::vector<PII>, std::greater<PII>> pq;
    //first - cost
    //second - target node id
    bool isNodeUsed[n+1] = {};
    isNodeUsed[1] = true;
    int numberOfUsedNodes = 1;
    long long totalCost = 0;

    // Add all edges from starting node
    for(auto edge : graph[1]) {
        pq.push(edge);
    }

    std::vector<std::vector<int>> graphS(n+1);
    while(numberOfUsedNodes < n && !pq.empty()) {
        auto [cost, targetNode] = pq.top();
        pq.pop();

        // Skip if node already in MST
        if(isNodeUsed[targetNode]) {
            continue;
        }

        // Add node to MST
        isNodeUsed[targetNode] = true;
        numberOfUsedNodes++;
        totalCost += cost;

        // Find which used node this edge connects from and add to graph
        for (auto [edgeCost, neighbor] : graph[targetNode]) {
            if (edgeCost == cost && isNodeUsed[neighbor]) {
                graphS[targetNode].push_back(neighbor);
                graphS[neighbor].push_back(targetNode);
                break;
            }
        }

        // Add all edges from newly added node to unused nodes
        for(auto edge : graph[targetNode]) {
            if (!isNodeUsed[edge.second]) {
                pq.push(edge);
            }
        }
    }

    output << totalCost << "\n";
    output << n-1 << "\n";
    for(int i = 1; i <= n; i++) {
        for(auto node : graphS[i]) {
            if(i < node) {
                output << i << " " << node << "\n";
            }
        }
    }

    return 0;
}