//! Algoritmul lui Kruskal de determinare a arborelui partial de cost minim
//! Varianta optima (Ologn)

#define MAX 200000
#include<iostream>
#include<fstream>
#include<algorithm>
using namespace std;


class edge
{
public:
    int x;
    int y;
    int c;
} A[MAX];
edge r[200000];
int tata[MAX],height[MAX];


int set_find(int u)      //gaseste multimea din care face parte un varf
{
    if(tata[u]==0)return u;     //daca varful e reprezentant al multimii (radacina a arborelui) returnam numarul lui
    else return set_find(tata[u]);     //daca nu, determinam recursiv reprezentantul multimii (radacina arborelui)
}

void set_merge(int u,int v,int height[MAX])       //reuniunea a 2 multimi
{
    if(height[u]>height[v])tata[v]=u;             //daca arborele(multimea) lui u este mai mare il adaugam pe v la el
    else
    {
        tata[u]=v;                             //daca nu, il adaugam pe u la arborele lui v
        if(height[u]==height[v])height[v]++;      //daca sunt egale ii crestem inaltimea lui v
    }
}


int compare(const void *a,const void *b)         //functie de comparare folosita in quicksort
{
    return ((*(edge*)a).c-(*(edge*)b).c);
}

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

    int n,   //nr de varfuri
    m,       //nr de muchii
    i,j,k,   //indici de parcurgeri
    nr=0,   //numarul curent de muchii din Arborele Economic
    u,v,
    total=0;

    f>>n>>m;
    for(k=0; k<m; k++) f>>A[k].x>>A[k].y>>A[k].c; //citire


    for(i=1; i<=n; i++)          //initializare arbore
    {
        tata[i]=0;           //fiecare varf e initial un arbore cu 1 nod
        height[i]=0;            //inaltimea lor e 0 by default
    }

    qsort(A,m,sizeof(edge),compare);        //sortarea muchiilor (quicksort)

    for(k=0; k<m &&nr<=n-1; k++) //Ne oprim cand nu mai avem muchii sau cand s-au adaugat n-1 muchii
    {
        u=set_find(A[k].x);    //aflam reprezentantul multimii primului varf al muchiei
        v=set_find(A[k].y);    //aflam reprezentantul multimii celui de-al doilea varf al muchiei
        if(u!=v)                       //daca sunt diferite cele 2 multimi indicate de reprezentanti
        {
            //cout<<"Muchia ("<<A[k].x<<","<<A[k].y<<") a fost adaugata"<<endl;
            r[nr].x=A[k].x;//
            r[nr].y=A[k].y;
            total+=A[k].c;
            //adaugam muchia in  Arborele Economic
            set_merge(u,v,height);     //unim cele 2 multimi
            nr++;          //crestem numarul de muchii adaugate in arbore
        }
        //else cout<<"Muchia ("<<A[k].x<<","<<A[k].y<<") a fost ignorata din motiv ca ar forma un ciclu"<<endl;
    }


   // cout<<endl<<"Prin urmare, arborele economic este format de: "<<endl;
g<<total<<"\n"<<nr<<"\n";
for(i=0; i<nr ; i++)
       g<<r[i].y<<" "<<r[i].x<<"\n";
    return 0;
}