#include <fstream>
#include <vector>
#include <algorithm>
#define cost first
#define x second.first
#define y second.second
using namespace std;

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

typedef vector<int> VI;
typedef pair<int, int> II;
typedef vector<II> VII;
typedef pair<int, II> III;
typedef vector<III> VIII;

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

void Read();
int Find(int a);
void Union(int a, int b);
void Write();

int main()
{
    Read();
    t = h = VI(n + 1);
    for ( int i = 1; i <= n; ++i )
        t[i] = i;
    sort(e.begin(), e.end());
    int tx, ty;
    m = n;
    for ( const auto &q : e )
    {
        tx = Find(q.x);
        ty = Find(q.y);
        if ( tx != ty )
        {
            Union(tx, ty);
            --n;
            answ.push_back(make_pair(q.x, q.y));
            c += q.cost;
            if ( n == 1 )
            {
                Write();
                is.close();
                os.close();
                return 0;
            }
        }
    }
}

void Write()
{
    os << c << "\n" << m - 1 << "\n";
    for ( const auto &q : answ)
        os << q.first << " " << q.second << "\n";
}

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

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

void Read()
{
    is >> n >> m;
    e = VIII(n + 1);
    III a;
    for ( int i = 1; i <= m; ++i )
    {
        is >> a.x >> a.y >> a.cost;
        e.push_back(a);
    }
}