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

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

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

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

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

int main()
{
    Read();
    Kruskal();
    os << apmcost << '\n';
    os << apm.size() << '\n';
    for ( const auto& a : apm )
        os << a.first << ' ' << a.second << '\n';

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


void Union(int x, int y)
{
    if ( h[x] > h[y] )
        t[y] = x;
    else
    {
        t[x] = y;
        if ( h[x] == h[y] )
            ++h[y];
    }
}

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

void Read()
{
    is >> n >> m;
    t = h = vector<int>(n + 1);
    int x, y, cost;
    for ( int i = 1; i <= m; ++i )
    {
        is >> x >> y >> cost;
        e.push_back({x, y, cost});
    }
}

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