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

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

const int INF_COST = INT_MAX;

using PerecheCostNod = std::pair<int, int>;
using ListaAdiacenta = std::vector<std::vector<PerecheCostNod>>;
using CoadaMinima = std::priority_queue<PerecheCostNod, std::vector<PerecheCostNod>, std::greater<PerecheCostNod>>;

int main() {
    int nrNoduri, nrMuchii;
    fin >> nrNoduri >> nrMuchii;

    ListaAdiacenta adj(nrNoduri + 1);
    for (int i = 0; i < nrMuchii; ++i) {
        int u, v, cost;
        fin >> u >> v >> cost;
        adj[u].push_back({v, cost});
        adj[v].push_back({u, cost});
    }

    std::vector<int> costMinim(nrNoduri + 1, INF_COST);
    std::vector<int> parinte(nrNoduri + 1, -1);
    std::vector<bool> inAPM(nrNoduri + 1, false);

    CoadaMinima pq;

    int nodStart = 1;
    costMinim[nodStart] = 0;
    pq.push({0, nodStart});

    long long costTotalAPM = 0;

    while (!pq.empty()) {
        int costCurent = pq.top().first;
        int nodCurent = pq.top().second;
        pq.pop();

        if (inAPM[nodCurent]) {
            continue;
        }

        inAPM[nodCurent] = true;
        costTotalAPM += costCurent;

        for (auto& muchie : adj[nodCurent]) {
            int vecin = muchie.first;
            int costMuchie = muchie.second;

            if (!inAPM[vecin] && costMuchie < costMinim[vecin]) {
                costMinim[vecin] = costMuchie;
                parinte[vecin] = nodCurent;
                pq.push({costMuchie, vecin});
            }
        }
    }

    fout << costTotalAPM << "\n";
    fout << nrNoduri - 1 << "\n";

    for (int i = 2; i <= nrNoduri; ++i) {
        fout << parinte[i] << ' ' << i << "\n";
    }

    return 0;
}