#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>
#include <set>

inline bool comp(std::pair<std::pair<int, int>, int> a, std::pair<std::pair<int, int>, int> b) {return a.second >= b.second;}

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::set<int> vizitati = {0};
    std::vector< std::pair<std::pair<int, int>, int> > inventar;
    std::vector<std::pair<int, int>> muchii;
    int cost = 0, nou_nod = 0;

    while (vizitati.size() < n)
    {
        for (auto vecin: vecini[nou_nod])
        {
            inventar.push_back({{nou_nod, vecin.first}, vecin.second});
            std::push_heap(inventar.begin(), inventar.end(), comp);
        }

        while (vizitati.find(inventar.front().first.second) != vizitati.end())
        {
            std::pop_heap(inventar.begin(), inventar.end(), comp);
            inventar.pop_back();
        }

        /*for (auto m: inventar)
        {
            out << m.first.first << ' ' << m.first.second << ' ' << m.second << '\n';
        }
        out << "\n\n\n";*/

        nou_nod = inventar.front().first.second;
        vizitati.insert(nou_nod);
        cost += inventar.front().second;
        muchii.push_back(inventar.front().first);

        std::pop_heap(inventar.begin(), inventar.end());
        inventar.pop_back();
    }

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

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

}