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

ifstream f("apm.in");
ofstream g("apm.out");

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N, M;
    if (!(f >> N >> M)) return 0;

    
    vector<vector<pair<int,int>>> adj(N + 1);
    adj.reserve(N + 1);

    for (int i = 0; i < M; ++i) {
        int X, Y, C;
        f >> X >> Y >> C;
        adj[X].push_back({Y, C});
        adj[Y].push_back({X, C});
    }

    
    using T = tuple<int,int,int>;
    priority_queue<T, vector<T>, greater<T>> pq;

    vector<char> inMST(N + 1, 0);
    vector<pair<int,int>> sol;  
    sol.reserve(N - 1);

    long long totalCost = 0;

    
    pq.push({0, 1, 0});

    int added = 0;
    while (!pq.empty() && added < N) {
        auto [c, u, p] = pq.top();
        pq.pop();

        if (inMST[u]) continue;
        inMST[u] = 1;
        totalCost += c;
        ++added;

        if (p != 0) sol.push_back({u, p}); 
        
        for (auto [v, w] : adj[u]) {
            if (!inMST[v]) pq.push({w, v, u});
        }
    }

    
    g << totalCost << "\n";
    g << (int)sol.size() << "\n";
    for (auto &e : sol) {
        
        g << e.first << " " << e.second << "\n";
    }

    return 0;
}