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

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

int n, m, cost;
vector<int> t, h;
vector<pair<int, pair<int, int> > > g;
vector<pair<int, int> > q;

int FIND(int x);
void UNION(int x, int y);
void KRUSKAL();
void READ();
void WRITE();

int main()
{
    READ();
    KRUSKAL();
    WRITE();
    is.close();
    os.close();
    return 0;
}

void KRUSKAL()
{
    int cnt = 0, nod1, nod2, t1, t2;
    for ( vector<pair<int, pair<int, int> > >::iterator it = g.begin(); it != g.end(); ++it )
    {
        nod1 = it->second.first;
        nod2 = it->second.second;
        t1 = FIND(nod1);
        t2 = FIND(nod2);
        if (  t1 != t2 )
        {
            UNION(t1, t2);
            cost += it->first;
            ++cnt;
            q.push_back(make_pair(nod1, nod2));
        }
        if ( cnt == n - 1 )
            return;
    }
}

void WRITE()
{
    os << cost << "\n" << n - 1 << "\n";
    for ( vector<pair<int, int> >::iterator it = q.begin(); it != q.end(); ++it )
        os << it->first << " " << it->second << "\n";
}

void READ()
{
    int x, y, z;
    is >> n >> m;
    t.resize(n + 1);
    h.resize(n + 1);
    for ( int i = 1; i <= n; ++i )
        t[i] = i;
    for ( int i = 1; i <= m; ++i )
    {
        is >> x >> y >> z;
        g.push_back(make_pair(z, make_pair(x, y)));
    }
    sort(g.begin(), g.end());
}

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

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