#include <bits/stdc++.h>
using namespace std;

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

struct elem {
    int nod1, nod2, cost;
};

const int nmax = 2e5 + 5;
int n, m, t[nmax], pret[nmax];
vector <elem> v;
vector <pair <int, int> > rasp;

elem make_elem(int x, int y, int c) {
    elem aux = {x, y, c};
    return aux;
}

bool cmp(elem a, elem b) {
    return a.cost < b.cost;
}

int findd(int x) {
    if (x != t[x]) return t[x] = findd(t[x]);

    return x;
}

void unite(int x, int y) {
    if (pret[x] < pret[y]) swap(x, y);

    t[y] = x;
    pret[x] += pret[y];
}

int main()
{
    fin >> n >> m;
    for (int i = 0; i < m; ++i) {
        int x, y, c;
        fin >> x >> y >> c;
        v.push_back(make_elem(x, y, c));
        t[x] = x;
        pret[x] = 1;
    }

    long long ans = 0;
    sort(v.begin(), v.end(), cmp);
    for (elem nr : v) {
        int nr1 = findd(nr.nod1);
        int nr2 = findd(nr.nod2);
        if (nr1 != nr2) {
            ans += nr.cost;
            unite(nr1, nr2);
            rasp.push_back({nr.nod1, nr.nod2});
        }
    }

    fout << ans << '\n' << rasp.size() << '\n';
    for (pair <int, int> x : rasp)
        fout << x.first << ' ' << x.second << '\n';
    return 0;
}