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

struct Edge {
    int to, cost;
};

int main() {
    ifstream f("apm.in");
    ofstream g("apm.out");
    int n, m;
    f >> n >> m;  

    vector<vector<Edge>> adj(n + 1);

    for (int i = 0; i < m; ++i) {
        int u, v, w;
        f >> u >> v >> w;
        adj[u].push_back({v, w});
        adj[v].push_back({u, w});
    }

    vector<bool> inMST(n + 1, false);
    vector<int> minCost(n + 1, numeric_limits<int>::max());
    vector<int> parent(n + 1, -1);
    vector<Edge> mst;


    int start = 1;
    minCost[start] = 0;

    
    priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>>> pq;
    pq.push({0, start});

    int totalCost = 0;

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

        if (inMST[u]) continue;
        inMST[u] = true;
        totalCost += cost;

        if (parent[u] != -1)
            mst.push_back({parent[u],u});

        for (const auto &edge : adj[u]) {
            int v = edge.to;
            int w = edge.cost;
            if (!inMST[v] && w < minCost[v]) {
                minCost[v] = w;
                parent[v] = u;
                pq.push({w, v});
            }
        }
    }
    g  << totalCost << "\n";
    g << mst.size() << "\n";
    for (const auto &e : mst) {
        g << e.cost  << " " << e.to <<"\n";
    }

    
    return 0;
}