#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>

using namespace std;

ifstream f ("apm.in");
ofstream g ("apm.out");

struct Muchie
{
    int nod1,nod2,cost;
};

int get_reprezentant(int nod,vector<int>&reprezentant)
{
    if(nod==reprezentant[nod])
        return nod;
    return reprezentant[nod]=get_reprezentant(reprezentant[nod],reprezentant);
}

bool cmpMuchie(Muchie m1,Muchie m2)
{
    return m1.cost<m2.cost;
}

bool verifica(int nod1,int nod2,vector<int>&reprezentant)
{
    return get_reprezentant(nod1,reprezentant)!=get_reprezentant(nod2,reprezentant);
}

void uneste(int nod1,int nod2,vector<int>&reprezentant,vector<int>&adancime,vector<vector<int>>&G)
{
    G[nod1].push_back(nod2);
    G[nod2].push_back(nod1);

    int rep_nod1=get_reprezentant(nod1,reprezentant);
    int rep_nod2=get_reprezentant(nod2,reprezentant);

    if(adancime[rep_nod1]<adancime[rep_nod2])
        reprezentant[rep_nod1]=rep_nod2;
    else
    {
        reprezentant[rep_nod2]=rep_nod1;
        if(adancime[rep_nod1]==adancime[rep_nod2])
            adancime[rep_nod1]++;
    }
}

int main()
{
    int n,m,i,cost_total;
    f>>n>>m;
    vector<vector<int>>G(n+1);
    vector<Muchie>M(m);
    vector<int>reprezentant(n+1);
    vector<int>adancime(n+1,0);

    for(i=1; i<=n; i++)
        reprezentant[i]=i;

    for(i=0; i<m; i++)
        f>>M[i].nod1>>M[i].nod2>>M[i].cost;

    sort(M.begin(),M.end(),cmpMuchie);

    cost_total=0;
    for(auto muchie:M)
        if(verifica(muchie.nod1,muchie.nod2,reprezentant))
        {
            cost_total+=muchie.cost;
            uneste(muchie.nod1,muchie.nod2,reprezentant,adancime,G);
        }

    g<<cost_total<<"\n";
    g<<n-1<<"\n";
    for(i=1; i<=n; i++)
    {
        for(auto vecin:G[i])
            if(i<vecin)
                g<<i<<" "<<vecin<<"\n";
    }

    return 0;
}