#include <fstream>
#include <vector>
#define oo 1e10

using namespace std;

struct neighbour{
    int c;
    int x;
};

vector<neighbour> L[200010];
int c[200010];
int fat[200010];
bool viz[200010];

vector<pair<int, int> > S;

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

    int n, m, x, y, z;
    f >> n >> m;
    neighbour aux;
    for(int i = 1; i <= m; i ++) {
        f >> x >> y >> z;
        aux.c = z;
        aux.x = y;
        L[x].push_back(aux);
        aux.x = x;
        L[y].push_back(aux);
    }

    int k = 1, C = 0;
    for(int i = 1; i <= n; i ++) c[i] = oo, fat[i] = i;
    c[1] = 0;

    int minimum = 0, p = 1;
    for(int i = 1; i <= n; i ++) {
        for(int j = 1; j <= n; j ++) {
            if(!viz[j] && c[j] < minimum) {
                minimum = c[j];
                p = j;
            }
        }
        viz[p] = true;
        S.push_back(make_pair(p, minimum));
        C += minimum;

        for(vector<neighbour>::iterator it = L[p].begin(); it != L[p].end(); it ++) {
            neighbour aux = *it;
            if(!viz[aux.x] && c[aux.x] > aux.c) {
                c[aux.x] = aux.c;
                fat[aux.x] = p;
            }
        }
        p = oo; minimum = oo;
    }

    g << C << "\n" << n - 1 << "\n";
    for(int i = 1; i < S.size(); i ++) {
        g << S[i].first << " " << fat[S[i].first] << "\n";
    }
    return 0;
}