#include <fstream>
#include <vector>
#include <algorithm>
#define pb push_back
#define mp make_pair

using namespace std;

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

vector <pair<int, pair<int, int> > > a;
vector <int> sol;

long long cost;

int n, m, x, y, c, rep[200005];

inline int reprezentant (int nod)
{
    if (rep[nod] != nod)
    {
        rep[nod] = reprezentant(rep[nod]);
    }

    return rep[nod];
}

bool verif (int x, int y)
{
    x = reprezentant(x);
    y = reprezentant(y);

    if (x != y) return true;

    return false;
}

void uneste (int x, int y)
{
    x = reprezentant(x);
    y = reprezentant(y);

    rep[x] = y;

}

int main()
{
    f >> n >> m;

    for (int i = 1; i <= m; i++)
    {
        f >> x >> y >> c;

        a.pb(mp(c, mp(x,y)));
    }

    for (int i = 1; i <= n; i++)
        rep[i] = i;

    sort(a.begin(), a.end());

    for (int i = 0; i < a.size(); i++)
    {
        if (verif(a[i].second.first, a[i].second.second) == true)
        {
            uneste(a[i].second.first, a[i].second.second);
            cost += a[i].first;
            sol.pb(i);
        }
    }

    g << cost << '\n';

    g << sol.size() << '\n';

    for (int i = 0; i < sol.size(); i++)
    {
        g << a[sol[i]].second.first << " " << a[sol[i]].second.second << '\n';
    }
    return 0;
}