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

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

using VI = vector<int>;
using VII = vector<pair<int, int>>;
using VIII = vector<pair<int, pair<int, int>>>;

int n, m, cost;
VI t, h;
VII answ;
VIII e;

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

int main()
{
    Read();
    sort(e.begin() + 1, e.end());
    t = h = VI(n + 1);
    for ( int i = 1; i <= n; ++i )
        t[i] = i;
    int x, y, xx, yy;
    for ( int i = 1, cnt = 1; i <= m && cnt < n; ++i )
    {
        x = e[i].second.first;
        y = e[i].second.second;
        xx = Find(x);
        yy = Find(y);
        if ( xx != yy )
        {
            ++cnt;
            Union(xx, yy);
            answ.push_back(make_pair(x, y));
            cost += e[i].first;
        }
    }
    Write();
    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 ( t[x] == x )
        return x;
    return x = Find(t[x]);
}

void Read()
{
    is >> n >> m;
    e = VIII(m + 1);
    int n1, n2;
    for ( int i = 1; i <= m; ++i )
    {
        is >> e[i].second.first;
        is >> e[i].second.second;
        is >> e[i].first;
    }
}

void Write()
{
    os << cost << "\n" << answ.size() << "\n";
    for ( const auto& i : answ )
        os << i.first << " " << i.second << "\n";
}