#include <fstream>
#include <vector>
#include <algorithm>
 
using namespace std;
 
ifstream fin("apm.in");
ofstream fout("apm.out");
 
struct Edge{
    int x, y, w;
    Edge ( int a = 0, int b = 0, int c = 0 )
        : x(a), y(b), w(c)
    {}
    bool operator < ( const Edge& e )   const
    {
        return w < e.w;
    }
};
 
vector<Edge> G;
vector<Edge> arb;
vector<int> t, h;
int n, m, cost_min, k;
 
void Read();
int Find(int x);
void Union(int x, int y);
void Kruskal();
void Write();
 
 
 
int main()
{
    Read();
    Kruskal();
    Write();
    return 0;
};
 
 
 
void Read()
{
    fin >> n >> m;
    t.resize(n + 1);
    h.resize(n + 1);
    for ( int i = 1; i <= n; ++i )
        t[i] = i, h[i] = 0;
    int x, y, w;
    while ( fin >> x >> y >> w )
        G.push_back(Edge(x, y, w));
};
 
int Find(int x)
{
    if ( x == t[x] )    return x;
    return t[x] = Find(t[x]);
};
 
void Union(int x, int y)
{
    if ( h[x] < h[y] )
        t[x] = y;
    else
    {
        t[y] = x;
        if ( h[x] == h[y] )
            h[x]++;
    }
};
 
void Kruskal()
{
    sort(G.begin(), G.end());
    int c1, c2;
 
    for ( const auto& e : G )
    {
        c1 = Find(e.x), c2 = Find(e.y);
        if ( c1 != c2 )
        {
            cost_min += e.w;
            arb.push_back(e);
            k++;
            Union(c1, c2);
 
            if ( k == n - 1 )
                return;
        }
    }
};
void Write()
{
    fout << cost_min << '\n' << k << '\n';
    for ( const auto& e : arb )
        fout << e.x << ' ' << e.y << '\n';
};