#include <fstream>
#include <vector>
#include <algorithm>

using namespace std;

ifstream fin("apm.in");
ofstream fout("apm.out");

#define MaxN 200001

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

class Graf
{
    public:

    Graf(int a, int b, int c) : x{a}, y{b}, z{c} {};

    bool operator < (const Graf& gr ) const
    {
        return ( z < gr.z || (z == gr.z && y < gr.y)
                || (z == gr.z && y == gr.y && x < gr.x) );
    }

    int x, y, z;
};

int n, m, cost;
vector<Graf> G;
int gr[MaxN];
VII sol;

int Union(int i)
{
    if ( gr[i] == i )
        return i;
    gr[i] = Union(gr[i]);
    return gr[i];
}

int main()
{
    fin >> n >> m;

    for ( int i = 1, x, y, z; i <= m; ++i )
    {
        fin >> x >> y >> z;
        G.push_back(Graf(x,y,z));
    }

    for ( int i = 1; i <= n; ++i )
        gr[i] = i;

    sort(G.begin(), G.end());

    for ( auto p : G )
    {
        if ( Union(p.x) != Union(p.y) )
        {
            cost += p.z;
            gr[Union(p.x)] = Union(p.y);
            sol.push_back({p.x, p.y});
        }
    }

    fout << cost << '\n' << n - 1 << '\n';

    for ( auto p : sol )
        fout << p.first << ' ' << p.second << '\n';

    fin.close();
    fout.close();
    return 0;
}