#include <iostream>
#include <fstream>
#include <queue>
using namespace std;

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

const int nrMaxNoduri = 200005;

struct Compara
{
    bool operator() (pair < int, int >  x, pair < int, int > y )
    {
        return x.second > y.second;
    }
};

priority_queue < pair < int, int >, vector < pair < int, int > >, Compara > heap ;

int n, m, nrNoduri, costTotal, nrMuchii;
bool inArbore[nrMaxNoduri];
pair < unsigned int, unsigned int > muchie[nrMaxNoduri];
queue < pair < int, int > > distanta[nrMaxNoduri];

void Citire()
{
    fin >> n >> m;
    nrNoduri = n;
    for (int i = 0; i < m; i++)
    {
        int x, y, cost;
        fin >> x >> y >> cost;
        distanta[x].push(make_pair(y, cost));
        distanta[y].push(make_pair(x, cost));
    }
}

void APM()
{
    inArbore[1] = true;
    nrNoduri--;
    while (!distanta[1].empty())
    {
        heap.push(distanta[1].front());
        distanta[1].pop();
    }

    int nodAnterior = 1;
    while (nrNoduri)
    {
        int nodActual, cost = heap.top().second;;
        nodActual = heap.top().first;
        heap.pop();
        if (!inArbore[nodActual])
        {
            //cout << nodAnterior << ' ' << nodActual << ' ' << cost << '\n';
            //muchie[nodActual] = nodAnterior;
            muchie[nrMuchii].first = nodAnterior;
            muchie[nrMuchii].second = nodActual;
            nodAnterior = nodActual;
            inArbore[nodActual] = true;
            costTotal += cost;
            nrNoduri--;
            nrMuchii++;
            while (!distanta[nodActual].empty())
            {
                int urmatorulNod = distanta[nodActual].front().first;
                heap.push(distanta[nodActual].front());
                distanta[nodActual].pop();
            }
        }

    }
}

void Afisare()
{
    fout << costTotal << '\n';
    fout << nrMuchii << '\n';
    for (int i = 0; i < nrMuchii; i++)
    {
        fout << muchie[i].first << ' ' << muchie[i].second << '\n';
    }
}

int main()
{
    Citire();
    APM();
    Afisare();
    return 0;
}