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

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

const int maxn = 400000;
int n, m;
vector<int> cost(maxn, maxn);  // cost[i] = costul minim
vector<int> parent(maxn, -1); // parent[i] = nodul din care am ajuns cel mai ieftin la i
vector<bool> inMST(maxn, false); // true dacă nodul este deja în APM
int totalCost = 0; // costul total al APM-ului
int main() {

    // citire si initializare
    fin >> n >> m;
    vector<vector<pair<int, int>>> adj(n + 1); // vectorul de adiacenta: nodul si costul

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

    // pornim de la primul nod
    cost[1] = 0;

    // heap pt muchia minima de forma cost-nod ca in cel de adiacenta
    priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>>> pq;

    pq.push({0, 1});

    // algoritmul efectiv
    while (!pq.empty()) {
        // iau din heap costul si nodul
        int currCost = pq.top().first;
        int u = pq.top().second;
        pq.pop();

        // trecem peste daca e deja in arbore
        if (inMST[u]) continue;
        inMST[u] = true; // il includem
        totalCost += currCost; // adaugam costul muchiei la costul total

        // parcurgem toate muchiile care ies din u
        for (auto [v, c] : adj[u]) {
            // verific daca am o varianta mai eficienta / rapida
            if (!inMST[v] && c < cost[v]) {
                cost[v] = c;
                parent[v] = u; // tinem minte de unde am venint
                pq.push({c, v}); // actualizam
            }
        }
    }

    /* verificare daca graful rezultat este conex sau nu ig
    for (int i = 1; i <= n; ++i) {
        if (cost[i] == maxn) {
            fout << "Graful nu este conex!\n";
            return 0;
        }
    } */

    // afisarea
    fout << totalCost << "\n";
    fout << n - 1 << "\n";

    // afișam muchiile parinte - fiu
    for (int i = 2; i <= n; ++i) {
        fout << parent[i] << " " << i << "\n";
    }

    return 0;
}