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

using namespace std;

struct neighbour{
    int c;
    int x;
};

vector<neighbour> L[200010];

vector<pair<int, int> > S;


int t;
int H[400110];
int poz[200010];

int c[200010];
int fat[200010];

void cobor(int x) {   //in heap
    while( (x * 2 <= t && c[H[x]] > c[H[x * 2]]) || (x * 2 + 1 <= t && c[H[x]] > c[H[x * 2 + 1]]) ) {
        if(c[H[x * 2]] < c[H[x * 2 + 1]] || x * 2 + 1 > t) {
            swap(H[x], H[x * 2]);
            swap(poz[H[x]], poz[H[x * 2]]);
            x *= 2;
        }
        else {
            swap(H[x], H[x * 2 + 1]);
            swap(poz[H[x]], poz[H[x * 2 + 1]]);
            x = x * 2 + 1;
        }
    }
}

int scot() { //din heap
    int aux = H[1];
    swap(H[1], H[t]);
    swap(poz[H[1]], poz[H[t]]);
    t --;
    cobor(1);
    poz[aux] = 0;
    return aux;
}

void urc(int x) {
    while(x > 1 && c[H[x]] < c[H[x / 2]]) {
        swap(H[x], H[x / 2]);
        swap(poz[H[x]], poz[H[x / 2]]);
        x /= 2;
    }
}

void in(int x) {
    t ++;
    H[t] = x;
    poz[x] = t;
    urc(t);
}

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;

    for(int i = 1; i <= n; i ++)
        in(i);

    for(int i = 1; i <= n; i ++) {
        int aux = scot();
        for(vector<neighbour>::iterator it = L[aux].begin(); it != L[aux].end(); it ++) {
            neighbour a = *it;
            if(c[a.x] > a.c) {
                c[a.x] = a.c;
                fat[a.x] = aux;
            }
        }
        for(vector<neighbour>::iterator it = L[aux].begin(); it != L[aux].end(); it ++) {
            neighbour a = *it;
            if(poz[a.x]) urc(poz[a.x]);
        }
        C += c[aux];
        S.push_back(make_pair(aux, fat[aux]));
    }

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