#include <bits/stdc++.h>
#include <fstream>
using namespace std;

struct Edge {
    int to, cost;
};

vector<vector<Edge>> G;
vector<int> parent;
vector<int> visited;

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

int main() {
    int N, M;
    fin >> N >> M;

    G.resize(N + 1);
    parent.assign(N + 1, -1);
    visited.assign(N + 1, 0);

    int x, y, c;
    for (int i = 0; i < M; i++) {
        fin >> x >> y >> c;
        G[x].push_back({y, c});
        G[y].push_back({x, c});
    }

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

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

    long long totalCost = 0;
    vector<pair<int,int>> edges; 
    edges.reserve(N - 1);

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

        if (visited[nod]) continue;

        visited[nod] = 1;
        totalCost += cost;

        if (par != -1) {
            edges.push_back({par, nod});
        }

        for (auto &e : G[nod]) {
            if (!visited[e.to]) {
                pq.push({e.cost, e.to, nod});
            }
        }
    }

    fout << totalCost << "\n";
    fout << edges.size() << "\n";
    for (auto &e : edges) {
        fout << e.first << " " << e.second << "\n";
    }

    return 0;
}