#include <vector>
#include <queue>
#include <fstream>
#include <algorithm>

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

const int LMAX = 400005;

struct muchie{
    int x, y, c;
};
muchie L[LMAX];
int father[LMAX/2], n;
bool ok;
vector <pair<int, int>> marb;

bool sortbyc(muchie a, muchie b) {
    return a.c < b.c;
}

int findroot(int x) {
    if (father[x] < 0) {
        return x;
    }
    int root =  findroot(father[x]);
    father[x] = root;
    return root;
}

void unite(int rx, int ry) {
    if (father[ry] < father[rx]) {
        swap(ry, rx);
    }
    father[rx]+=father[ry];
    father[ry] =  rx;
    if (father[rx] * (-1) == n) {
        ok = 1;
    }
}

int main() {
    int m, ct;
    fin>>n>>m;
    for (int i = 1; i <= n; i++) {
        father[i] = -1;
    }
    for (int i = 0; i < m; i++) {
        fin>>L[i].x>>L[i].y>>L[i].c;
    }
    sort(L, L+m, sortbyc);
    ct = 0;
    for (int i = 0; i < m && !ok; i++) {
        int rx, ry;
        rx = findroot(L[i].x);
        ry = findroot(L[i].y);
        if (rx != ry) {
            unite(rx, ry);
            ct+=L[i].c;
            marb.push_back({L[i].x, L[i].y});
        }
    }
    fout<<ct<<endl;
    fout<<marb.size()<<endl;
    for (int i = 0; i < marb.size(); i++) {
        fout<<marb[i].first<<" "<<marb[i].second<<endl;
    }


    fin.close();
    fout.close();

    return 0;
}