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

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

struct Muchie
{
    int a,b,cost;
};

struct Muchie_a_b
{
    int a,b;
};

bool cmp(Muchie a,Muchie b)
{
    return a.cost<b.cost;
}

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

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

void uneste(int a,int b,vector<int>&parinte,vector<int>&adancime)
{
    int repa=reprezentant(a,parinte);
    int repb=reprezentant(b,parinte);

    if(adancime[repa]<adancime[repb])
        parinte[repa]=repb;
    else
        parinte[repb]=repa;

    if(adancime[repa]==adancime[repb])
        adancime[repa]++;
}

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

    for(i=0; i<=n; i++)
        parinte[i]=i;

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

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

    cost_total=0;
    index=0;
    for(auto muc:M)
        if(verifica(muc.a,muc.b,parinte))
        {
            cost_total+=muc.cost;
            uneste(muc.a,muc.b,parinte,adancime);
            index++;
            G[index].a=muc.a;
            G[index].b=muc.b;
        }

    g<<cost_total<<"\n";
    g<<index<<"\n";
    for(i=1; i<=index; i++)
        g<<G[i].a<<" "<<G[i].b<<"\n";

    return 0;
}