#include <bits/stdc++.h>
using namespace std;


int primMST(int numberOfNodes, vector<vector<pair<int, int>>> &adjList, int& numberOfEdgesUsed, vector<int> &parent) {
    vector<int> dist(numberOfNodes, INT_MAX);
    vector<bool> visited(numberOfNodes, false);
    priority_queue<pair<int, int>> q;
    int totalCost = 0;
    dist[0] = 0;
    q.push({0, 0});

    while (!q.empty()) {
        if (not visited[q.top().second]) {
            int u = q.top().second;
            totalCost -= q.top().first;
            numberOfEdgesUsed++;
            q.pop();
            visited[u] = true;

            for (auto neighbor: adjList[u]) {
                int v = neighbor.first;
                int weight = neighbor.second;

                if (!visited[v] && weight < dist[v]) {
                    dist[v] = weight;
                    parent[v] = u;
                    q.push({-weight, v});
                }
            }
        }
        else
            q.pop();
    }

    return totalCost;
}

int main() {
    ifstream input("apm.in");

    int numberOfNodes, numberOfEdges;
    input>>numberOfNodes>>numberOfEdges;

    vector<vector<pair<int,int>>> adjacencyList(numberOfNodes, vector<pair<int,int>>());
    int firstNode, secondNode, cost;
    for (int i=0; i< numberOfEdges; i++) {
        input>>firstNode>>secondNode>>cost;
        firstNode--; secondNode--;
        adjacencyList[firstNode].emplace_back(secondNode, cost);
        adjacencyList[secondNode].emplace_back(firstNode, cost);
    }

    input.close();

    ofstream output("apm.out");
    int numberOfEdgesUsed = -1;
    vector<int> parentOf(numberOfNodes, -1);

    output<<primMST(numberOfNodes, adjacencyList, numberOfEdgesUsed, parentOf)<<'\n'<<numberOfEdgesUsed<<'\n';

    for (int i = 1; i < numberOfNodes; i++) {
        output << i+1 << " " << parentOf[i]+1 << "\n";
    }

    output.close();

    return 0;
}