#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;
ifstream in("apm.in");
ofstream out("apm.out");
int n, m, v[100010], i, c;
vector<pair<int, int>> vel;
struct tripla
{
    int x, y, cost;
}a[400010];
bool sortfnc(tripla a, tripla b)
{
    return a.cost < b.cost;
}
int fnd(int k)
{
    if (k == v[k])
        return k;
    v[k] = fnd(v[k]);
    return v[k];
}
void unite(int x, int y)
{
    int tx = fnd(x);
    int ty = fnd(y);
    v[tx] = ty;
}
int main()
{
    in >> n >> m;
    for (i = 1; i <= n; i++)
        v[i] = i;
    for (i = 1; i <= m; i++)
        in >> a[i].x >> a[i].y >> a[i].cost;
    sort(a+1, a+1+m, sortfnc);
    for (i = 1; i <= m; i++)
    {
        if (fnd(a[i].x) == fnd(a[i].y))
            continue;
        else
        {
            unite(a[i].x, a[i].y);
            vel.push_back(make_pair(a[i].x, a[i].y));
            c += a[i].cost;
        }
    }
    out << c << '\n' << vel.size() << '\n';
    for (auto ind : vel)
        out << ind.first << ' ' << ind.second << '\n';
}