#include <fstream>
#include <algorithm>
#include <vector>
#define NMAX 200005
#define MMAX 400005

using namespace std;
ifstream in("apm.in");
ofstream out("apm.out");

struct edge{
    int x, y, cost;
};

edge v[MMAX];
vector < edge > newTree;
bool cmp(edge a, edge b)
{
    return a.cost < b.cost;
}

int father[NMAX];

int f(int x)
{
    if (x == father[x])
        return x;
    else
        return father[x] = f(father[x]);
}

void unite(int x, int y)
{
    int father_x = f(x);
    int father_y = f(y);

    if (father_x != father_y)
    {
        father[father_x] = father_y;
    }
}

int main()
{
    int n, m, i, j;
    long long treeCost = 0;
    in >> n >> m;
    for (i = 1; i <= m; ++i)
        in >> v[i].x >> v[i].y >> v[i].cost;
    sort (v + 1, v + m + 1, cmp);

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

    for (i = 1; i <= m; ++i)
    {
        if (f(v[i].x) != f(v[i].y))
        {
            unite(v[i].x, v[i].y);
            newTree.push_back({v[i].x, v[i].y, v[i].cost});
            treeCost = treeCost + v[i].cost;
        }
    }

    out << treeCost << '\n' << newTree.size() << '\n';
    for (i = 0; i < newTree.size(); ++i)
        out << newTree[i].x << " " << newTree[i].y << '\n';

    /*for (i = 1; i <= m; ++i)
        out << v[i].x << " " << v[i].y << " " << v[i].cost << '\n';*/
    return 0;
}