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

using namespace std;

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

const int nmax = 200005;
long long n, m, cost, T[nmax];
vector< pair< int, pair<int, int> > > a;
vector< pair<int, int> > sol;

int get_root(int nod)
{
    if(T[nod] > 0)
    {
        T[nod] = get_root(T[nod]);
        return T[nod];
    }

    else
        return nod;
}

int Join(int x, int y)
{
    int rx = get_root(x);
    int ry = get_root(y);

    if(rx == ry)
        return 0;

    if(T[rx] >= T[ry])
    {
        T[rx] += T[ry];
        T[ry] = rx;
    }

    else
    {
        T[ry] += T[rx];
        T[rx] = ry;
    }
    return 1;
}

void Kruskal()
{
    sort(a.begin(), a.end());
    for(int i = 0; i < a.size(); i ++)
    {
        int x, y, c, r1, r2;
        x = a[i].second.first;
        y = a[i].second.second;
        c = a[i].first;

        if(Join(x, y))
        {
            cost += c;
            sol.push_back({y, x});
        }
    }
}

int main()
{
    f >> n >> m;
    for(int i = 1; i <= m; i ++)
    {
        int x, y, c;
        f >> x >> y >> c;
        a.push_back(mp(c, mp(x, y)));
    }

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

    Kruskal();

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