#include <fstream>
#include <algorithm>
#include <vector>
using namespace std;

ifstream is("apm.in");
ofstream os("apm.out");

int n, m;
int x, y;
int tot, cnt;
int gr[200001];

struct Edge{
    int n1, n2, w;
};

Edge e[400001];

vector <pair <int, int> > sol;

bool CMP(const Edge &e1, const Edge &e2)
{
    return e1.w < e2.w;
}

int Grupa(int i)
{
    if (gr[i] == i)
        return gr[i];
    gr[i] = Grupa(gr[i]);
    return gr[i];
}

void Leaga(int i, int j)
{
    gr[Grupa(i)] = Grupa(j);
}

int main()
{
    is >> n >> m;
    for (int i = 1; i <= m; ++i)
        is >> e[i].n1 >> e[i].n2 >> e[i].w;

    sort(e + 1, e + m + 1, CMP);

    for (int i = 1; i <= m; ++i)
        gr[i] = i;

    for (int i = 1; i <= m; ++i)
    {
        x = e[i].n1, y = e[i].n2;
        if ( Grupa(x) != Grupa(y) )
        {
            cnt++;
            tot += e[i].w;
            Leaga(x, y);
            sol.push_back(make_pair(x, y));
        }

        if (cnt > n - 1)
            break;
    }

    os << tot << '\n' << cnt << '\n';
    for (int i = 0; i < sol.size(); ++i)
        os << sol[i].first << ' ' << sol[i].second << '\n';

    is.close();
    os.close();
    return 0;
}