#include <fstream>
#define NMAX 5002

using namespace std;

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

int n, m, comp[NMAX];   /// comp - marcheaza componentele conexe; initial, toate vf = izolate
struct muchii {
    int a, b;
    int cost;
} mu[NMAX], rez[NMAX];

void citire() {
    fin >> n >> m;
    for(int i = 1; i <= m; i++)
        fin >> mu[i].a >> mu[i].b >> mu[i].cost;
}

void ordonare() {
    for(int i = 1; i < m; i++)
        for(int j = i + 1; j <= m; j++) {
            if(mu[j].cost < mu[i].cost){
                muchii c = mu[i];
                mu[i] = mu[j];
                mu[j] = c;
            }
        }
}

int kruskal() {
    for(int i = 1; i <= n; i++) comp[i] = i;

    int cost = 0;
    int ms = 0; /// nr muchii selectate
    int ctr = 0;

    while(ms != n - 1) {
        do {
            ctr++;
        } while(comp[mu[ctr].a] == comp[mu[ctr].b]);

        ms++;
        int a1 = comp[mu[ctr].a];
        int b1 = comp[mu[ctr].b];
        int mini, maxi;

        if(a1 > b1) {
            mini = b1;
            maxi = a1;
        }
        else {
            mini = a1;
            maxi = b1;
        }

        rez[ms] = mu[ctr];
        cost += mu[ctr].cost;

        for(int i = 1; i <= n; i++)
            if(comp[i] == maxi)
                comp[i] = mini;
    }

    fout << cost << '\n';
    for(int i = 1; i <= n - 1; i++)
        fout << mu[i].a << ' ' << mu[i].b << '\n';
}

int main()
{
    citire();
    ordonare();
    kruskal();
    return 0;
}