#include <iostream>
#include <fstream>
#include <vector>
#include <queue>


//cu Prim
using namespace std;

struct muchie
{
    int din,spre,cost;
    bool operator()(const muchie &x, const muchie &y)
    {
        return x.cost > y.cost;
    }
};

struct cmp
{
    bool operator() ( const muchie &a , const muchie &b ) const
    {
        if ( a.cost < b.cost ) return 1;
        return 0;
    }
};

#define N_MAX 200000

int n,m,suma_totala,numarul_muchiilor;
vector < pair <int,int> > vecin[N_MAX];//primul e spre cine, al doilea costul
priority_queue <muchie, vector<muchie>, cmp> muchii_posibile;
vector < pair<int,int> > raspuns;

void citire()
{
    ifstream f("apm.in");
    f >> n >> m;
    int i,x,y,cost;
    for(i = 0; i < m; i++)
    {
        f >> x >> y >> cost;
        --x;--y;
        vecin[x].push_back(make_pair(y,cost));
        vecin[y].push_back(make_pair(x,cost));
    }
    f.close();
}

bool apm_terminat()
{
    static int i=0;
    for(;i<n;++i)
    {
        if(!vecin[i].empty())
            return false;
    }
    return true;
}

void expand(int nod)
{
    muchie adaugata;
    adaugata.din = nod;
    for(unsigned int i=0;i<vecin[nod].size();++i)
    {
        if(!vecin[vecin[nod][i].first].empty())
        {
            adaugata.spre = i;
            adaugata.cost = vecin[nod][i].second;
            muchii_posibile.push(adaugata);
        }
    }
    vecin[nod].clear();
}

void apm()
{
    //luam ca start 0
    expand(0);int i=0;
    muchie urmatoarea_muchie;
    while(!apm_terminat())
    {
        do
        {
            urmatoarea_muchie = muchii_posibile.top();
            muchii_posibile.pop();
        }
        while(vecin[urmatoarea_muchie.spre].empty());
        suma_totala += urmatoarea_muchie.cost;
        numarul_muchiilor ++;
        expand(urmatoarea_muchie.spre);
    }
}

void afisare()
{
    ofstream g("apm.out");
    g<<suma_totala<<endl<<numarul_muchiilor;
    for(unsigned int i=0;i<raspuns.size();++i)
        g<<endl<<raspuns[i].first<<" "<<raspuns[i].second;
    g.close();
}

int main()
{
    citire();
    suma_totala = 0;
    numarul_muchiilor = 0;
    apm();
    afisare();
    return 0;
}