#include <bits/stdc++.h>
#define inf 2147483647

using namespace std;

vector< pair<int, int> > L[200005];
int c[200005];
int t[200005];
int h[200005], l;
int pz[200005];

void swith(int &a, int &b) {
    int aux = a;
    a = b;
    b = aux;
}

void apm(int x) {
    for(int i = 0; i < L[x].size(); i ++) {
        int where = L[x][i].first;
        int much = L[x][i].second;
        if(c[where] > much)
            c[where] = much, t[where] = x;
    }
}

void cobor(int poz) {
    int ls = poz * 2;
    int rs = poz * 2 + 1;
    int where = 0;
    if(rs < l) {
        if(h[rs] < h[ls])
            where = rs;
        else where = ls;
    }
    else if(ls < l) {
        where = ls;
    }

    if(c[h[where]] < c[h[poz]]) {
        swith(h[where], h[poz]);
        swith(pz[h[where]], pz[h[poz]]);
        cobor(where);
    }
}

void urc(int poz) {
    int tata = poz / 2;
    if(tata > 0 && c[h[tata]] > c[h[poz]]) {
        swith(h[tata], h[poz]);
        swith(pz[h[tata]], pz[h[poz]]);
        urc(tata);
    }
}

void heap(int x) {
    l ++;
    h[l] = x;
    pz[x] = l;
    urc(l);
}

int first() {
    int ret = h[1];
    h[1] = h[l];
    l --;

    swith(pz[ret], pz[h[1]]);
    cobor(1);
    pz[ret] = l + 1;
    return ret;
}

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

    int n, m, X, Y, C;

    f >> n >> m;
    for(int i = 1; i <= m; i ++) {
        f >> X >> Y >> C;
        L[X].push_back(make_pair(Y, C));
        L[Y].push_back(make_pair(X, C));
    }

    for(int i = 1; i <= n; i ++)
        c[i] = inf;
    h[0] = 0;
    c[0] = inf;
    c[1] = 0;
    apm(1);

    for(int i = 2; i <= n; i ++) {
        heap(i);
    }

    int ans = 0;
    vector<pair<int, int>> ret;
    for(int i = 2; i <= n; i ++) {
        int x = first();
        apm(x);
        ans += c[x];
        ret.push_back(make_pair(x, t[x]));
        for(int j = 0; j < L[x].size(); j ++) {
            if(pz[L[x][j].first] <= l)
                urc(pz[L[x][j].first]);
        }

    }

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