#include <iostream>
#include <vector>
#include <queue>
#include <tuple>
#include <fstream>
using namespace std;

int primMST(int n, vector<vector<pair<int, int>>>& graph,
    vector<pair<int, int>>& sol) {

    vector<bool> visited(n, false);

    priority_queue<tuple<int, int, int>,vector<tuple<int, int, int>>,greater<tuple<int, int, int>>> pq;

    visited[0] = true;
    for (auto& edge : graph[0]) {
        pq.push({ edge.second, 0, edge.first });
    }

    long long totalCost = 0;

    while (!pq.empty()) {
        auto [cost, u, v] = pq.top();
        pq.pop();

        if (visited[v]) continue;

        visited[v] = true;
        totalCost += cost;
        sol.push_back({ u, v });

        for (auto& edge : graph[v]) {
            if (!visited[edge.first]) {
                pq.push({ edge.second, v, edge.first });
            }
        }
    }

    return totalCost;
}

int main() {
    

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

    int N, M;
    fin >> N >> M;

    vector<vector<pair<int, int>>> graph(N);

    for (int i = 0; i < M; i++) {
        int u, v, c;
        fin >> u >> v >> c;
        u--, v--; 
        graph[u].push_back({ v, c });
        graph[v].push_back({ u, c });
    }

    vector<pair<int, int>> sol; 
    long long totalCost = primMST(N, graph, sol);

  
    fout << totalCost << endl;
    fout << sol.size() << endl;

    
    for (auto& e : sol) {
        fout << e.first + 1 << " " << e.second + 1 << endl;
    }

    return 0;
}