#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 findSetRoot(int x)
{
    if (sett[x] == x)
        return x;
    int aux = findSetRoot(sett[x]);
    return aux;
}

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];
        int x = findSetRoot(a.u);
        int y = findSetRoot(a.v);
        if (x != y)
        {
            Cost += a.w;
            arbore.push_back(a);
            sett[x] = y;
        }
    }

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