#include <bits/stdc++.h>

using namespace std;

#define NMAX 200010
#define INF (1 << 30)

class Task {
public:
    void solve() {
        read_input();
        get_result();
        print_output();
    }

private:
    int n, m;

    // p[i] = parintele lui i de pe drumul minim de la source la nodul i
    vector<int> p;

    vector<pair<int, int>> adj[NMAX];

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

    vector<int> d;

    vector<int> used;

    int apm;

    void read_input() {
        cin >> n >> m;
        p = vector<int>(n + 1);
        d = vector<int>(n + 1, INF);
        used = vector<int>(n + 1, 0);
        for (int i = 1; i <= m; ++i) {
            // citim muchii x -> y, de cost c
            int x, y, c;
            cin >> x >> y >> c;
            adj[x].push_back({c, y});
            adj[y].push_back({c, x});
        }
    }

    void get_result() {
        Prim();
    }

    void Prim() {
        apm = 0;
        int root = 1;
        d[root] = 0;
        p[root] = 0;
        pq.push({d[root], root});
        for (int i = 1; i <= n; ++i){
            int node;
            do {
                auto edge = pq.top();
                pq.pop();
                node = edge.second;
            } while (used[node]);
            used[node] = 1;
            apm += d[node];
            for (auto &edge : adj[node]) {
                int cost = edge.first;
                int vecin = edge.second;
                if (!used[vecin] && cost < d[vecin]) {
                    d[vecin] = cost;
                    p[vecin] = node;
                    pq.push({cost, vecin});
                }
            }
        }
    }

    void print_output() {
        cout << apm << '\n';
        cout << n - 1 << '\n';
        for (int i = 2; i <= n; ++i) {
            cout << p[i] << ' ' << i << '\n';
        }
    }
};

int main() {
    // din cauza ca fac redirectari, salvez starea lui cin si cout
    auto cin_buff = cin.rdbuf();
    auto cout_buff = cout.rdbuf();

    // las liniile urmatoare daca citesc din fisier
    ifstream fin("apm.in");
    cin.rdbuf(fin.rdbuf()); // save and redirect

    // las liniile urmatoare daca afisez in fisier
    ofstream fout("apm.out");
    cout.rdbuf(fout.rdbuf()); // save and redirect

    // aici este rezolvarea propriu-zisa
    Task *task = new Task();
    task->solve();
    delete task;

    // restore pentru cin si cout
    cin.rdbuf(cin_buff);
    cout.rdbuf(cout_buff);

    // obs. nu e nevoie sa inchid fisierele
    // cand se apeleaza destructorii pentru fin si fout se vor inchide

    return 0;
}