#define submit
#ifdef submit
    #define fisier "apm"
#else
    #define fisier "ULTRA"
#endif

#include <fstream>
std::ifstream in(fisier ".in");
std::ofstream out(fisier ".out");

#include <vector>
std::vector<std::pair<int, int>> vecini[200000];
int n;

#include <algorithm>

int main()
{
    int m;
    in >> n >> m;

    while (m--)
    {
        int a, b, c;
        in >> a >> b >> c;
        a--; b--;

        vecini[a].push_back({b, c});
        vecini[b].push_back({a, c});
    }

    std::vector<int> vizitati = {0};
    std::vector<std::pair<int, int>> muchii;
    int cost = 0;

    while (vizitati.size() < n)
    {
        std::pair<int, int>
        min_vecin = {-1, 1001},
        min_muchie = {0, min_vecin.first};

        int min_sursa = 0;

        /*out << "\nvizitati = ";
        for (int viz: vizitati)
            out << viz+1 << " ";
        out << "\n";*/

        for (int nod: vizitati)
        {
            //out << "    nod = " << nod+1 << "\n";
            for (auto vecin: vecini[nod])
            {
                //out << "        vecin = " << vecin.first+1 << "\n";
                if (vecin.second < min_vecin.second && std::find(vizitati.begin(), vizitati.end(), vecin.first) == vizitati.end())
                {
                    //out << "            adaugat\n";
                    min_vecin = vecin;
                    min_muchie = {nod, min_vecin.first};
                }
            }
        }

        vizitati.push_back(min_vecin.first);
        muchii.push_back(min_muchie);
        cost += min_vecin.second;
    }

    out
    << cost << '\n'
    << n - 1 << '\n';

    for (auto muchie: muchii)
        out << muchie.first+1 << ' ' << muchie.second+1 << '\n';

}