#include <fstream>
#include <algorithm>

using namespace std;

ifstream cin ("apm.in");
ofstream cout ("apm.out");

struct graf
{
    int x, y, cost, viz;
}v[400001];

int n, m, sef[200001], c, edges;

bool cmp(graf a, graf b)
{
    if(a.cost < b.cost)
        return 1;
    return 0;
}

int boss(int x)
{
    if(x == sef[x])
        return x;
    else
        return sef[x] = boss(sef[x]);
}

void join(int x, int y)
{
    sef[boss(x)] = boss(y);
}

int main()
{
    cin >> n >> m;
    for(int i = 1; i <= m; ++i)
        cin >> v[i].x >> v[i].y >> v[i].cost;
    for(int i = 1; i <= n; ++i)
        sef[i] = i;
    sort(v + 1, v + 1 + m, cmp);
    for(int i = 1; i <= m; ++i)
    {
        if(boss(v[i].x) != boss(v[i].y))
        {
            join(v[i].x, v[i].y);
            c += v[i].cost;
            v[i].viz = 1;
            edges++;
        }
    }
    cout << c << '\n' << edges << '\n';
    for(int i = 1; i <= m; ++i)
        if(v[i].viz == 1)
            cout << v[i].x << " " << v[i].y << '\n';
    return 0;
}