#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <set>
#include <chrono>

using namespace std;

ifstream f("apm.in");
ofstream g("apm.out");

struct arc
{
    int u, v;
    double w;

    bool operator<(const arc &a) const
    {
        return w < a.w;
    }
};

int V, E, *sett;
int N, Cost;
vector<arc> arbore;

int main()
{
    f >> V >> E;
    vector<arc> arce(E + 1);
    for (int i = 1; i <= E; i++)
    {
        f >> arce[i].u >> arce[i].v >> arce[i].w;
    }
    sort(arce.begin() + 1, arce.end());

    sett = new int[V + 1];
    for (int i = 1; i <= V; i++)
    {
        sett[i] = i;
    }

    for (int i = 1; i <= E; i++)
    {
        arc a = arce[i];
        if (sett[a.u] != sett[a.v])
        {
            Cost += a.w;
            arbore.push_back(a);
            int set_v = sett[a.v];
            for (int j = 1; j <= V; j++)
            {
                if (sett[j] == set_v)
                {
                    sett[j] = sett[a.u];
                }
            }
        }
    }

    g << Cost << '\n';
    g << arbore.size() << '\n';
    for (auto &a : arbore)
    {
        g << a.u << ' ' << a.v << '\n';
    }
    return 0;
}