#include <bits/stdc++.h>

using namespace std;

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

int x, y, cost, n, m, TT[200005], costTotal;

struct muchii
{
        int x, y, cost;
        muchii() {}
        muchii(int a, int b, int c)
        {
                x = a;
                y = b;
                cost = c;
        }
};

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

int root(int nod)
{
        int R = nod, next;
        while(TT[R] != R) R = TT[R];

        while(TT[nod] != nod)
        {
                next = TT[nod];
                TT[nod] = R;
                nod = next;
        }

        return R;
}

void unite(int x, int y)
{
        TT[y] = x;
}

muchii v[400005];

vector <muchii> edges, sol;
vector <muchii> :: iterator it;

int main()
{
        f >> n >> m;
        for(int i = 1; i <= m; ++i)
        {
                f >> x >> y >> cost;
                edges.push_back(muchii(x, y, cost));
        }

        for(int i = 1; i <= n; ++i) TT[i] = i;
        sort(edges.begin(), edges.end(), cmp);

        for(it = edges.begin(); it != edges.end(); ++it)
        {
                int radX = root((*it).x);
                int radY = root((*it).y);
                if(radX != radY)
                {
                        costTotal += (*it).cost;
                        unite(radX, radY);
                        sol.push_back(muchii((*it).x, (*it).y, 0));
                }
        }

        g << costTotal << '\n' << n - 1 << '\n';
        for(it = sol.begin(); it != sol.end(); ++it) g << (*it).x << " " << (*it).y << '\n';
        return 0;
}