#include <fstream>
#include <algorithm>
#include <queue>

using namespace std;

ifstream F("apm.in");
ofstream G("apm.out");

queue <pair <int, int> > sol;
pair <int, pair <int, int> > edge[400003];
int f[200003], x, y, w, n, m, mst_e, mst_ni, mst_w, fx, fy;

int fnd(int x)
{
    while(x != f[x])
        x = f[x];
    return x;
}

void Unite(int x, int y)
{
    f[y] = x;
}

int main()
{
    F >> n >> m;
    for(int i = 1; i <= n; ++ i)
        f[i] = i;
    for(int i = 0; i < m; ++ i)
    {
        F >> x >> y >> w;
        edge[i].first = w;
        edge[i].second.first = x;
        edge[i].second.second = y;
    }
    sort(edge, edge + m);
    while((mst_e < n - 1) || (mst_ni < m))
    {
        w = edge[mst_ni].first;
        x = edge[mst_ni].second.first;
        y = edge[mst_ni].second.second;
        fx = fnd(x);
        fy = fnd(y);
        if(fx != fy)
        {
            Unite(fx, fy);
            mst_w += w;
            mst_e ++;
            sol.push({x, y});
        }
        mst_ni ++;
    }
    G << mst_w << '\n';
    G << n - 1 << '\n';
    while(!sol.empty())
        G << sol.front().second << " " << sol.front().first << '\n', sol.pop();
    return 0;
}