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

using VI = vector<int>;

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

struct Edge {
    int x, y, cost;
    inline bool operator < ( const Edge& c ) const
    {
        return cost < c.cost;
    }
};

void Kruskal();
void Union(int x, int y);
int Find(int x);
void Read();
void Write();

vector<Edge> e;
VI p, h;
vector<pair<int, int> > apm;
int n, m, apmcost;

int main()
{
    Read();
    Kruskal();
    Write();

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

void Kruskal()
{
    sort(e.begin(), e.end());
    for ( int i = 1; i <= n; ++i )
        p[i] = i;
    int x, y;
    for ( size_t i = 0; i < e.size() && apm.size() < unsigned(n - 1); ++i )
    {
        x = Find(e[i].x);
        y = Find(e[i].y);
        if ( x != y )
        {
            Union(x, y);
            apm.push_back({e[i].x, e[i].y});
            apmcost += e[i].cost;
        }
    }
}
void Union(int x, int y)
{
    if ( h[x] > h[y] )
        p[y] = x;
    else
    {
        p[x] = y;
        if ( h[x] == h[y] )
            ++h[y];
    }
}

int Find(int x)
{
    if ( x != p[x] )
        p[x] = Find(p[x]);
    return p[x];
}

void Read()
{
    is >> n >> m;
    p = h = VI(n + 1);
    for ( int i = 1, x, y, cost; i <= m; ++i )
    {
        is >> x >> y >> cost;
        e.push_back({x, y, cost});
    }
}
void Write()
{
    os << apmcost << '\n';
    os << apm.size() << '\n';
    for ( const auto& a : apm )
        os << a.first << ' ' << a.second << '\n';
}