#include <fstream>
#include <vector>
#include <queue>
#include <limits>

using namespace std;

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

const int NMAX = 200001;
const int INF = numeric_limits<int>::max();

int n, m;
vector<pair<int, int>> adj[NMAX];
vector<int> dist;
vector<int> parent;
vector<bool> viz;
long long total_cost = 0;

int main() {
    fin >> n >> m;

    dist.resize(n + 1, INF);
    parent.resize(n + 1, 0);
    viz.resize(n + 1, false);

    for (int i = 0; i < m; i++) {
        int x, y, cost;
        fin >> x >> y >> cost;
        adj[x].push_back({y, cost});
        adj[y].push_back({x, cost});
    }

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

    dist[1] = 0;
    pq.push({0, 1});

    int muchii = 0;

    while (!pq.empty() && muchii < n) {
        int d = pq.top().first;
        int u = pq.top().second;
        pq.pop();

        if (viz[u]) {
            continue;
        }

        viz[u] = true;
        total_cost += d;
        muchii++;

        for (auto& edge : adj[u]) {
            int v = edge.first;
            int cost_uv = edge.second;
            if (!viz[v] && cost_uv < dist[v]) {
                dist[v] = cost_uv;
                parent[v] = u;
                pq.push({dist[v], v});
            }
        }
    }

    fout << total_cost << '\n';
    fout << n - 1 << '\n';
    for (int i = 2; i <= n; ++i) {
        fout << parent[i] << ' ' << i << '\n';
    }

    return 0;
}