/// Prim, O(N^2)
#include <fstream>
#include <vector>

using namespace std;

int n, m, i, j, k, nod, cmin, minim;
int d[10005], tata[10005];
bool viz[10005];
vector<pair<int, int>> arbore, v[10005];

int main() {
    ifstream f("apm.in");
    ofstream g("apm.out");

    int infinit = 2000000000;

    f >> n >> m;
    while(m) {
        f >> i >> j >> k;
        v[i].emplace_back(j, k);    /// muchie i->j, cu costul k
        v[j].emplace_back(i, k);    /// muchie j->i, cu costul k
        m--;
    }

    for(i = 1; i <= n; i++) {
        viz[i] = false;    /// toate nodurile de la 2 la n sunt nevizitate
        d[i] = infinit;    /// distanta de la un nod din arbore la i
        tata[i] = 0;       /// tatal nodului i in arbore
    }
    d[1] = 0;
    cmin = 0;   /// costul arborelui
    for(k = 1; k <= n; k++) {
        minim = infinit;
        nod = -1;
        for(j = 1; j <= n; j++)
            if(!viz[j] && d[j] < minim) {
                minim = d[j];
                nod = j;    /// aleg nodul nevizitat cu eticheta d[j] minima
            }
        viz[nod] = true;
        for(j = 0; j < v[nod].size(); j++)  /// pentru toti vecinii nevizitati ai lui nod
            if(!viz[v[nod][j].first] && v[nod][j].second < d[v[nod][j].first]) {    /// actualizez eticheta d[vecin]
                d[v[nod][j].first] = v[nod][j].second;
                tata[v[nod][j].first] = nod;
            }
        if(nod != 1) {
            arbore.emplace_back(nod, tata[nod]);
            cmin += minim;
        }
    }

    g << cmin << '\n';
    for(i = 0; i < arbore.size(); i++)
        g << arbore[i].first << ' ' << arbore[i].second << '\n';
    g.close();

    return 0;
}