#include <iostream>
#include <list>
#include <fstream>
#include <stack>
#include <vector>
#include <climits>

using namespace std;

// ifstream fin("input.txt");
// ofstream fout("output.txt");

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

vector<pair<int,int> > v;

class graf {
private:
    int n;
    bool este_orientat;
    bool muchiile_au_cost;
    list<int> *ad;
    list<int> *cost;

public:
    graf(int n=1, bool o=1, bool c=0) {
        this->n = n;
        this->este_orientat = o;
        this->muchiile_au_cost = c;
        this->ad = new list<int>[n];
        this->cost = new list<int>[n];
    };

    void adaug_muchie(int v, int w, int cst=INT_MAX) {
        if (este_orientat == 1) {
            this->ad[v].push_back(w);

            if (muchiile_au_cost)
                this->cost[v].push_back(cst);
        }  
        else {
            this->ad[v].push_back(w);
            this->ad[w].push_back(v);

            if (muchiile_au_cost) {
                this->cost[v].push_back(cst);
                this->cost[w].push_back(cst);
            }
        }
    };

    void BFS(int s);
    void distante(int s);

    void DFS(int s);
    void DFS_recursiv(int s, bool *vizitat);
    int nr_conexe();

    int* sortaret();
    void dfs_top(int &ind, int i, bool* vizitat, int* sortare);

    int* bellman_ford();

    graf prim();
    int* gaseste_muchie(bool* vizitate);
    void afisare_muchii();
};

void graf::BFS(int s) {
    bool *vizitat = new bool[n];
    for (int i = 0; i < n; i++) {
        vizitat[i] = false;
    }

    list<int> coada;
    vizitat[s] = true;
    coada.push_back(s);

    while(!coada.empty()) {
        list<int>::iterator i;

        s = coada.front();
        fout << s << " ";
        // fout << s+1 << " ";

        coada.pop_front();

        for (i = ad[s].begin(); i != ad[s].end(); i++) {
            if (vizitat[*i] == false) {
                vizitat[*i] = true;
                coada.push_back(*i);
            }
        }
    }
    delete[] vizitat;
}

void graf::distante(int s) {
    bool *vizitat = new bool[n];
    int *distante = new int[n];
    for (int i = 0; i < n; i++) {
        vizitat[i] = false;
        distante[i] = -1;
    }

    list<int> coada;
    vizitat[s] = true;
    coada.push_back(s);
    distante[s] = 0;

    while(!coada.empty()) {
        list<int>::iterator i;

        s = coada.front();
        coada.pop_front();

        for (i = ad[s].begin(); i != ad[s].end(); i++) {
            if (vizitat[*i] == false) {
                vizitat[*i] = true;
                distante[*i] = distante[s] + 1;
                coada.push_back(*i);
            }
        }
    }

    for (int i = 0; i < n; i++) {
        fout << distante[i] << " ";
    }

    delete[] vizitat;
    delete[] distante;
}

void graf::DFS(int s) {
    bool *vizitat = new bool[n];
    for (int i = 0; i < n; i++) {
        vizitat[i] = false;
    }

    DFS_recursiv(s, vizitat);
    delete[] vizitat;
}

void graf::DFS_recursiv(int s, bool *vizitat) {
    vizitat[s] = true;
    // fout << s << " ";

    list<int>::iterator it;

    for (it = ad[s].begin(); it != ad[s].end(); it++) {
        if (!vizitat[*it])
            DFS_recursiv(*it, vizitat);
    }
}

int graf::nr_conexe() {
    bool *vizitat = new bool[n];
    for (int i = 0; i < n; i++) {
        vizitat[i] = false;
    }
    int nr = 0;

    for (int i = 0; i < n; i++) {
        if (!vizitat[i]) {
            DFS_recursiv(i, vizitat);
            nr ++;
        }
    }

    delete[] vizitat;
    return nr;
}

int* graf::sortaret() {
    bool *vizitat = new bool[n];
    int *sortare = new int[n];
    for (int i = 0; i < n; i++) {
        vizitat[i] = false;
        sortare[i] = -1;
    }

    int ind = n - 1;

    for (int i = 0; i < n; i++) {
        if (!vizitat[i]) {
            dfs_top(ind, i, vizitat, sortare);
        }
    }

    delete[] vizitat;
    return sortare;
}

void graf::dfs_top (int &ind, int i, bool* vizitat, int* sortare) {
    vizitat[i] = true;

    list<int>::iterator it;

    for (it = ad[i].begin(); it != ad[i].end(); it++) {
        if (!vizitat[*it]) {
            dfs_top(ind, *it, vizitat, sortare);
        }
    }


    sortare[ind] = i;
    ind --;
}

int* graf::bellman_ford() {
    int* distante = new int[n];
    distante[0] = 0;
    for (int i = 1; i < n; i++) {
        distante[i] = INT_MAX;
    }
    int contor = 0;

    for (int i = 0; i < n-1; i++) {
        for (int nod = 0; nod < n; nod++) {
            if (distante[nod] != INT_MAX) {
                list<int>::iterator it, cst = cost[nod].begin();

                for (it = ad[nod].begin(); it != ad[nod].end(); it++) {
                    if (distante[nod] + (*cst) < distante[*it] && *it != 0) {
                        distante[*it] = distante[nod] + (*cst);
                        contor = 1;
                    }
                    cst++; 
                }
            }
        }
        if (contor == 0) { // daca deja am ajuns la distantele minime
            break;
            return distante;
        }
        else contor = 0;
    }

    for (int nod = 0; nod < n; nod++) {
            list<int>::iterator it, cst = cost[nod].begin();

            for (it = ad[nod].begin(); it != ad[nod].end(); it++) {
                if (distante[nod] + (*cst) < distante[*it]  && *it != 0) {
                    fout << "Ciclu negativ!";
                    return NULL;
                }
                cst++; 
            }
        }

    return distante;
}

graf graf::prim() {
    graf apm(n, 0, 1);
    int cost_total = 0;

    bool* vizitate = new bool[n];
    for (int i = 0; i < n; i++) {
        vizitate[i] = 0;
    }
    vizitate[0] = 1;
    
    
    for (int i = 0; i < n - 1; i++) {
        int* t = this->gaseste_muchie(vizitate);
        apm.adaug_muchie(t[0], t[1], t[2]);
        v.push_back({t[0], t[1]});
        vizitate[t[1]] = 1;
        cost_total += t[2];
        delete[] t;
    }

    // printf("%d\n%d\n", cost_total, (n - 1));
    fout << cost_total << '\n' << n - 1 << '\n';
    return apm;
}

int* graf::gaseste_muchie(bool* vizitate) {
    int* valori = new int[3];
    int x, y, mincost = INT_MAX;

    for (int i = 0; i < n; i++) {
        bool este_vizitat = vizitate[i];
        if (este_vizitat) {
            list<int>::iterator it, cst;
            cst = cost[i].begin();

            for (it = ad[i].begin(); it != ad[i].end(); it++) {
                if (!vizitate[*it]) {
                    if (*cst < mincost) {
                        mincost = *cst;
                        x = i;
                        y = *it;
                    }
                }
                cst++; 
            } 
        }
        
    }

    valori[0] = x;
    valori[1] = y;
    valori[2] = mincost;
    return valori;
}

void graf::afisare_muchii() {
    for (int i = 0; i < n; i++) {

    }  
}

int main() {
    int n, m, a, b, c;
    fin >> n >> m;
    graf g(n, 0, 1);

    for (int i = 0; i < m; i++) {
        fin >> a >> b >> c;
        g.adaug_muchie(a-1, b-1, c);
    }

    graf apm = g.prim(); 
    vector<pair<int, int> >::iterator it;
    for (it = v.begin(); it != v.end(); it++) {
        fout << (*it).first + 1 << " " << (*it).second + 1 << '\n';
    }
    
    return 0;
}