#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 x){
    if (tata[x] == x)
        return x;

    return tata[x] = reprez(tata[x]);
}


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';
}