#include <iostream>
#include <fstream>
#include <vector>
#include <list>
#include <queue>

using namespace std;

using Muchie = pair<int,int>;
using Vecin = pair<int,int>;

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

int n,m,costMin;
vector<Vecin> G[200001]; // graful citit
bool F[200001]; // pt fiecare nod true = "l-am bagat in arborele partial"
list<Muchie> Mmin; // rezultatul

struct MuchieComp
{
    MuchieComp(int first, int second, int c)
    {
        this->first = first;
        this->second = second;
        this->c = c;
    }

    int first,second,c;

    bool operator < (const MuchieComp& other) const
    {
        return c > other.c;
    }
};

void APM()
{
    priority_queue<MuchieComp> Mqueue;
    F[1] = true;
    for (const Vecin& v : G[1])
        Mqueue.emplace(1, v.first, v.second);

    while (!Mqueue.empty())
    {
        MuchieComp m = Mqueue.top();
        Mqueue.pop();

        if (F[m.second] == false) // daca punctul pe care vreau sa il leg este izolat (nu l-am mai legat de arbore)
        {
            F[m.second] = true;
            Mmin.emplace_back(m.first, m.second);
            costMin += m.c;
            for (const Vecin& v : G[m.second]) // dupa ce adaug un nod ii pun si toate muchiile vecine lui
                Mqueue.emplace(m.second, v.first, v.second);
        }
    }
}

int main()
{
    fin >> n >> m;
    for (int i = 1; i <= m; ++i)
    {
        int x,y,c;
        fin >> x >> y >> c;
        G[x].emplace_back(y, c);
        G[y].emplace_back(x, c);
    }
    APM();
    fout << costMin << '\n';
    fout << Mmin.size() << '\n';
    for (const Muchie& m : Mmin)
        fout << m.first << " " << m.second << '\n';

    return 0;
}