#include <fstream>
#include <vector>

using namespace std;

const int INF = 2e8 + 1;

struct muchie {
    int x, y, c;
    int celalalt(int vf) {
        return (x + y - vf);
    }
};

vector <int> h, d, poz_in_h;
vector <vector <int>> lst_a;

void schimb(int p1, int p2) {
    swap(h[p1], h[p2]);
    poz_in_h[h[p1]] = p1;
    poz_in_h[h[p2]] = p2;
}

void coboara(int p) {
    int fs = 2 * p + 1, fd = 2 * p + 2, poz = p;
    if (fs < (int)h.size() && d[h[fs]] < d[h[poz]]) {
        poz = fs;
    }
    if (fd < (int)h.size() && d[h[fd]] < d[h[poz]]) {
        poz = fd;
    }
    if (poz != p) {
        schimb(poz, p);
        coboara(poz);
    }
}

void sterge() {
    schimb(0, (int)h.size() - 1);
    h.pop_back();
    coboara(0);
}

void adauga(int x) {
    h.push_back(x);
    poz_in_h[x] = (int)h.size() - 1;
}

void urca(int p) {
    while (p != 0 && d[h[p]] < d[h[(p-1)/2]]) {
        schimb(p, (p - 1) / 2);
        p = (p - 1) / 2;
    }
}

int main() {
    ifstream in("apm.in");
    ofstream out("apm.out");
    int n, m;
    in >> n >> m;
    h.reserve(n);
    d.resize(n + 1, INF);
    poz_in_h.resize(n + 1);
    vector <int> vecin_apm(n + 1);
    vector <bool> in_apm(n + 1, false);
    for (int i = 1; i <= n; i++) {
        adauga(i);
    }
    vector <muchie> e(m);
    lst_a.resize(n + 1);
    for (int i = 0; i < m; i++) {
        in >> e[i].x >> e[i].y >> e[i].c;
        lst_a[e[i].x].push_back(i);
        lst_a[e[i].y].push_back(i);
    }
    // pornim din 1 (nu e conectat la APM prin alt varf)
    d[1] = 0;
    vecin_apm[1] = 0;
    in_apm[1] = true;
    int cost = 0;
    for (int i = 0; i < n; i++) {
        int x = h[0];
        cost += d[x];
        // out << "aleg " << x << " cu " << d[x] << "\n";
        in_apm[x] = true;
        sterge();
        for (auto i: lst_a[x]) {
            int y = e[i].celalalt(x);
            if (!in_apm[y] && e[i].c < d[y]) {
                d[y] = e[i].c;
                vecin_apm[y] = x;
                urca(poz_in_h[y]);
            }
        }
    }
    out << cost << "\n" << n - 1 << "\n";
    for (int i = 2; i <= n; i++) {
        out << i << " " << vecin_apm[i] << "\n";
    }
    in.close();
    out.close();
    return 0;
}