#include <iostream>
#include <fstream>
#include <limits.h>
#include <vector>
#include <queue>
using namespace std;

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

struct Muchie
{
    int vecin, cost;

    bool operator<(const Muchie &obj) const
    {
        return this->cost > obj.cost; //> pt min-heap
    }
};

vector<vector<Muchie>> generare_liste_adiacenta_cost(int varfuri, int muchii)
{
    vector<vector<Muchie>> lista(varfuri);
    int x, y, cost;
    for (int i = 0; i < muchii; i++)
    {
        fin >> x >> y >> cost;
        lista[x - 1].push_back({y, cost});
        lista[y - 1].push_back({x, cost});
    }
    return lista;
}

void Prim(int n, int m, int s, vector<vector<Muchie>> &lista_adiacenta_cu_cost,
          vector<pair<int, int>> &muchii_apcm, long long &cost)
{

    priority_queue<Muchie> minHeap; // va folosi comparatia definita in struct;
    vector<int> d(n + 1, INT_MAX);
    vector<int> tata(n + 1, -1);
    vector<bool> inHeap(n + 1, true);

    d[s] = 0;
    minHeap.push({s, d[s]});

    while (!minHeap.empty())
    {
        int u = minHeap.top().vecin;
        cout << u << endl;
        minHeap.pop();
        inHeap[u] = false;

        for (const auto &muchie : lista_adiacenta_cu_cost[u - 1])
        {
            int v = muchie.vecin;
            int cost_muchie = muchie.cost;

            if (inHeap[v] && cost_muchie < d[v])
            {
                d[v] = cost_muchie;
                tata[v] = u;
                minHeap.push({v, d[v]});
            }
        }
    }

    for (int i = 1; i <= n; i++)
        if (i != s)
            muchii_apcm.push_back({i, tata[i]}), cost += d[i];
}

int main()
{
    int n, m;
    fin >> n >> m;
    vector<vector<Muchie>> liste_adiacenta_cu_cost = generare_liste_adiacenta_cost(n, m);
    fin.close();

    vector<pair<int, int>> muchii_apcm;
    long long cost = 0;

    Prim(n, m, 1, liste_adiacenta_cu_cost, muchii_apcm, cost);

    fout << cost << '\n'
         << n - 1 << '\n';
    for (const auto &muchie : muchii_apcm)
        fout << muchie.first << " " << muchie.second << '\n';
    fout.close();
    return 0;
}