#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <functional>
#include <climits>

using namespace std;

ifstream fin("apm.in");
ofstream fout("apm.out");

struct Muchie {
    int a, b, w;
    bool operator>(const Muchie& other) const {
        return w > other.w; // For min-heap
    }
};

int main() {
    int n, m, x, y, c;
    fin >> n >> m;

    vector<vector<pair<int, int>>> adjList(n + 1);
    while (fin >> x >> y >> c) {
        adjList[x].push_back({y, c});
        adjList[y].push_back({x, c});
    }

    vector<bool> visited(n + 1, false);
    vector<int> parent(n + 1, -1);

    // Priority queue for min-heap of edges by weight
    priority_queue<Muchie, vector<Muchie>, greater<Muchie>> pq;

    // Start Prim's algorithm from node 1
    int startNode = 1;
    visited[startNode] = true;

    // Insert all edges from startNode into the priority queue
    for (auto& [neighbor, weight] : adjList[startNode]) {
        pq.push({startNode, neighbor, weight});
    }

    int totalCost = 0;
    vector<Muchie> result;

    while (!pq.empty()) {
        Muchie minEdge = pq.top();
        pq.pop();

        // Skip if destination node is already in the MST
        if (visited[minEdge.b]) continue;

        // Add edge to MST and mark node as visited
        visited[minEdge.b] = true;
        totalCost += minEdge.w;
        result.push_back(minEdge);

        // Add all edges from the new node to the priority queue
        for (auto& [neighbor, weight] : adjList[minEdge.b]) {
            if (!visited[neighbor]) {
                pq.push({minEdge.b, neighbor, weight});
            }
        }
    }

    // Output results
    fout << totalCost << endl;
    fout << result.size() << endl;
    for (auto& edge : result) {
        fout << edge.a << " " << edge.b << endl;
    }

    return 0;
}