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


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

struct Muchie_ponderata
{
    int x,y,cost;
};

struct Muchie
{
    int x,y;
};

bool cmp_muchii (Muchie_ponderata m1,Muchie_ponderata m2)
{
    return m1.cost<m2.cost;
}

int reprezentant (int x, vector<int>&parinte)
{
    if (x==parinte[x])
        return x;

    return reprezentant(parinte[x],parinte);
}

void reuneste (int nod1,int nod2,vector<int>&adancime,vector<int>&parinte)
{
    int rep1=reprezentant(nod1,parinte);
    int rep2=reprezentant(nod2,parinte);

    if (adancime[rep1]<adancime[rep2])
        parinte[rep1]=rep2;
    else
        parinte[rep2]=rep1;

    if (adancime[rep1]==adancime[rep2])
        adancime[rep1]++;
}

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

int main()
{
    int n,m,cod,x,y;

    f>>n>>m;

    vector<Muchie_ponderata> Muchii(m);

    for (int i=0;i<m;i++)
        f>>Muchii[i].x>>Muchii[i].y>>Muchii[i].cost;

    sort(Muchii.begin(),Muchii.end(),cmp_muchii);

    vector<int>parinte(n+1);
    for (int i=1; i<=n; i++)
        parinte[i]=i;

    vector<int>adancime (n+1,0);
    vector<Muchie> G(n-1);

    int cost_total=0,i=0;

    for (auto muchie:Muchii)
        if (verifica(muchie.x,muchie.y,parinte))
    {
        reuneste(muchie.x,muchie.y,adancime,parinte);
        G[i].x=muchie.x;
        G[i].y=muchie.y;
        i++;
        cost_total+=muchie.cost;
    }

    g<<cost_total<<endl<<n-1<<endl;

    for (auto muchie:G)
        g<<muchie.x<<" "<<muchie.y<<endl;
}