#include <fstream>
#include <vector>
#include <queue>
#include <climits>
using namespace std;
struct muchie
{
    int fiu;
    int cost;
};
struct CompareCost
{
    bool operator()(muchie const & muc1, muchie const &muc2)
    {
        return muc1.cost > muc2.cost;
    }
};
int main()
{
    int n, m;
    ifstream f("apm.in");
    ofstream g("apm.out");

    f >> n >> m;

    vector<vector<muchie>> lista_adiacenta(n+1);
    int a, b, c;
    for(int i = 0; i < m; i++)
    {
        f >> a >> b >> c;
        muchie muc;
        muc.fiu = b;
        muc.cost = c;
        lista_adiacenta[a].push_back(muc);
        muc.fiu = a;
        lista_adiacenta[b].push_back(muc);
    }

    int distante_apm[n + 1];
    int tati[n + 1];
    bool vizitat[n + 1];
    for(int i = 0; i <= n; i++)
    {
        distante_apm[i] = INT_MAX;
        tati[i] = 0;
        vizitat[i] = false;
    }
    priority_queue<muchie, vector<muchie>, CompareCost> coada;
    vector<muchie> sol;
    muchie muc;
    muc.cost = 0;
    muc.fiu = 1;
    coada.push(muc);
    distante_apm[1] = 0;
    int i = 0, sum = 0;
    while(i < n)
    {
        muchie minim = coada.top();
        coada.pop();

        if(vizitat[minim.fiu] == false)
        {
            vizitat[minim.fiu] = true;
            sum = sum + minim.cost;
            i++;
            muc.cost = tati[minim.fiu];
            muc.fiu = minim.fiu;
            sol.push_back(muc);

            for(int j = 0; j < lista_adiacenta[minim.fiu].size(); j++)
            {
                muc = lista_adiacenta[minim.fiu][j];
                if(vizitat[muc.fiu] == false && distante_apm[muc.fiu] > muc.cost)
                {
                    distante_apm[muc.fiu] = muc.cost;
                    tati[muc.fiu] = minim.fiu;
                    coada.push(muc);
                }
            }
        }
    }
    g << sum << "\n" << n - 1 << "\n";
    for(int i = 1; i < sol.size(); i++)
    {
        g << sol[i].cost << " " << sol[i].fiu << "\n";
    }
    return 0;
}