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

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

class nod_graf
{
public:
    int val_muchie;
    int nr_nod;
};

class val_heap
{
public:
    int cost_muchie, nr_nod, coming_from;
    bool operator<(const val_heap &x) const
    {
        return cost_muchie > x.cost_muchie;
    }
};

vector<nod_graf> G[200005];
vector<int> capete_muchie[200005];
priority_queue<val_heap> min_heap;
long long N, M, cost_total, nr_muchii;
bool vizitat[200005];

void mst()
{
    val_heap root;
    root.cost_muchie = 0;
    root.nr_nod = 1;
    root.coming_from = 0;
    min_heap.push(root);
    while (!min_heap.empty())
    {
        while (!min_heap.empty() && vizitat[min_heap.top().nr_nod])
            min_heap.pop();
        if (min_heap.empty())
            break;
        val_heap nod = min_heap.top();
        cout << nod.nr_nod << "\n";
        nr_muchii++;
        capete_muchie[nod.coming_from].push_back(nod.nr_nod);
        min_heap.pop();
        cost_total += nod.cost_muchie;
        vizitat[nod.nr_nod] = true;
        for (int i = 0; i < G[nod.nr_nod].size(); i++)
        {
            val_heap nod_nou;
            nod_nou.cost_muchie = G[nod.nr_nod][i].val_muchie;
            nod_nou.nr_nod = G[nod.nr_nod][i].nr_nod;
            nod_nou.coming_from = nod.nr_nod;
            min_heap.push(nod_nou);
        }
    }
}

int main()
{
    int X, Y, C;
    fin >> N >> M;
    for (int i = 1; i <= M; i++)
    {
        fin >> X >> Y >> C;
        nod_graf nod;
        nod.val_muchie = C;
        nod.nr_nod = Y;
        G[X].push_back(nod);
        nod.nr_nod = X;
        G[Y].push_back(nod);
    }
    mst();
    fout << cost_total << "\n"
         << nr_muchii - 1 << "\n";
    for (int i = 1; i <= N; i++)
    {
        for (int j = 0; j < capete_muchie[i].size(); j++)
            fout << i << " " << capete_muchie[i][j] << "\n";
    }
    return 0;
}