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

using namespace std;

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

int n, cost, t[200005];
priority_queue <pair <int, pair <int, int> > > coada;
vector <pair <int, int> > sol;

inline int dad(int x)
{
    if(t[x] == x) return x;
    else return t[x] = dad(t[x]);
}

void APM()
{
    for(int i = 1; i <= n; ++i) t[i] = i;

    int tx, ty;
    while(!coada.empty())
    {
        tx = dad(coada.top().second.first);
        ty = dad(coada.top().second.second);
        if(tx != ty)
        {
            cost += -coada.top().first;
            sol.push_back(make_pair(coada.top().second.first, coada.top().second.second));
            t[tx] = ty;
        }
        coada.pop();
    }
}

int main()
{
    int m;
    fin >> n >> m;
    for(int i = 1, x, y, c; i <= m; ++i)
    {
        fin >> x >> y >> c;
        coada.push(make_pair(-c, make_pair(x, y)));
    }
    fin.close();

    APM();
    fout << cost << '\n' << n-1 << '\n';
    for(int i = 0; i < sol.size(); ++i) fout << sol[i].first << " " << sol[i].second << '\n';
    fout.close();
    return 0;
}