#include <bits/stdc++.h>

using namespace std;

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

int n, m, i, nr1, nr2, nr3, t1, t2;
long long sum;
vector <int> tata(200001), lvl(200001);

int reprez(int i){
    int ci = i, aux;
    while (i != tata[i])
        i = tata[i];
    while (ci != i){
        aux = ci;
        ci = tata[ci];
        tata[aux] = i;
    }
    return i;
}

void unesc(int a, int b){
    int tataa = reprez(a), tatab = reprez(b);
    if (lvl[tataa] > lvl[tatab])
        tata[tatab] = tataa;
    else
        tata[tataa] = tatab;
    if (lvl[tataa] == lvl[tatab])
        ++lvl[tatab];
}

int main()
{
    fin >> n >> m;
    vector <vector <int>> lmuc(m);
    for(i = 0; i < m; ++i){
        fin >> nr1 >> nr2 >> nr3;
        lmuc[i] = {nr3, nr1, nr2};
    }
    sort(lmuc.begin(), lmuc.end());

    for (i = 1; i <= n; ++i){
        tata[i] = i;
    }
    vector <pair<int, int>> lmucNou;
    for (i = 0; i < m; ++i){
        nr1 = lmuc[i][1];
        nr2 = lmuc[i][2];
        nr3 = lmuc[i][0];
        t1 = reprez(nr1);
        t2 = reprez(nr2);
        if (t1 != t2){
            lmucNou.push_back({nr1, nr2});
            unesc(nr1, nr2);
            sum += nr3;
        }
    }
    fout << sum << '\n' << lmucNou.size() << '\n';
    for (auto &k : lmucNou){
        fout << k.first << ' ' << k.second << '\n';
    }
    return 0;
}