#include <fstream>
#include <cstring>
#include <iostream>
#include <vector>
using namespace std;

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

#define INF 9999999
#define N 20001

int G[N][N];
int ocupat[N];

int main() {
    int n, m, nrMuchii, s = 0;
    fin >> n >> m;
    int a, b, c;

    vector<pair<int, int>> add;

    for (int i = 1; i <= m; ++i) {
        fin >> a >> b >> c;
        G[a][b] = G[b][a] = c;
    }

    nrMuchii = 1;///numarul de muchii
    ocupat[1] = 1;

    int x, y;

    while (nrMuchii < n) {///cat timp mai sunt muchii de adaugat
        int min = INF;
        x = 0;
        y = 0;

        for (int i = 1; i <= n; i++) {
            if (ocupat[i]) {///daca punctul i nu e deja adaugat
                for (int j = 1; j <= n; j++) {
                    if (!ocupat[j] && G[i][j]) {  //daca punctul j nu e deja adaugat si exista muchie i-j
                        if (min > G[i][j]) {///luam muchia de cost minim
                            min = G[i][j];
                            x = i;
                            y = j;
                        }
                    }
                }
            }
        }
        ocupat[y] = 1;
        nrMuchii++;
        s += G[x][y];
        add.push_back({ x, y });
    }
    fout << s << "\n";
    for (int i = 0; i < add.size(); ++i)
        fout << add[i].first << " " << add[i].second << "\n";
    return 0;
}