#include <bits/stdc++.h>

using namespace std;

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

struct edge{
    int i, j, w;
};

bool cmp(edge x, edge y)
{
    return x.w < y.w;
}

vector <edge> edges, mst;

int n, m, tata[200001], sz[200001], total;

int reprez (int i)
{
    while (i != tata[i])
        i = tata[i];
    return i;
}

void reunion (int x, int y)
{
    int rx = reprez(x);
    int ry = reprez(y);

    if (sz[rx] > sz[ry])
        tata[ry] = rx, sz[rx] += sz[ry];
    else
        tata[rx] = ry, sz[ry] += sz[rx];
}

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

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

    sort(edges.begin(), edges.end(), cmp);

    for (auto e : edges)
        if (reprez(e.i) != reprez(e.j) and mst.size() < n)
    {
        total += e.w;
        reunion(e.i, e.j);
        mst.push_back(e);
    }

    g<<total<<'\n'<<mst.size()<<'\n';
    for (auto e : mst)
        g<<e.i<<' '<<e.j<<'\n';
}