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

#define MAXN 200002
#define MAXM 400002

using namespace std;

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

vector <int> sol;

struct trei{
    int x, y, z;
};

trei muchie[MAXM];
int tata[MAXN], n, m, cost;

inline bool cum(trei a, trei b)
{
    return a.z < b.z;
}

inline void Read()
{
    fin >> n >> m;

    for (int i = 1; i <= m; i++)
        fin >> muchie[i].x >> muchie[i].y >> muchie[i].z;
}

inline int search(int nod)
{
    if (tata[nod] != nod) ///daca nu am gasit radacina arborelui
    {
        search(tata[nod]); ///merg inapoi pe noduri pana la radacina
    }
    return tata[nod];
}

inline void APM(void)
{
    int p1, p2;

    for (int i = 1; i <= n; i++)
        tata[i] = i; ///initial avem n componente conexe, fiecare formata dintr-un nod

    for (int i = 1; i <= m; i++)
    {

        p1 = search(muchie[i].x); ///determin componenta conexa din care face parte nodul x
        p2 = search(muchie[i].y); ///determin componenta conexa din care face parte nodul y

        if (p1 != p2) ///daca fac parte din componente conexe diferite
        {
            tata[p1] = p2; ///componentele conexe p1 si p2 se unifica, iar p1 devine fiul lui p2

            cost += muchie[i].z;
            sol.push_back(i);
        }
    }
}

inline void Afisare(void)
{
    fout << cost << "\n" << sol.size() << "\n";

    for (vector <int> :: iterator i = sol.begin(); i != sol.end(); i++)
    {
        fout << muchie[*i].x << " " << muchie[*i].y << "\n";
    }
}

int main ()
{
    Read();

    sort(muchie + 1, muchie + m + 1, cum);

    APM();
    Afisare();

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