//Arbore partial de cost minim (Kruskal)
#include <iostream>
#include <fstream>
using namespace std;
ifstream in("apm.in");
ofstream out("apm.out");

int n,m,s;
struct muchie{
    int n1,n2,c;
    bool used;
}mch[400005],aux;
int M[200005]; //M[i] - retine multimea in care se afla nodul i

void citire()
{
    in>>n>>m;
    for(int i=1;i<=m;++i)
        in>>mch[i].n1>>mch[i].n2>>mch[i].c;
}

void quicksort(int st,int dr)
{
    int i=st,j=dr;
    muchie mij=mch[st+(dr-st)/2];

    do{
        while(i<dr && mch[i].c<mij.c)
            ++i;
        while(j>st && mch[j].c>mij.c)
            --j;
        if(i<=j)
        {
            aux=mch[i], mch[i]=mch[j], mch[j]=aux;
            ++i, --j;
        }
    }while(i<=j);

    if(i<dr) quicksort(i,dr);
    if(j>st) quicksort(st,j);
}

void kruskal()
{
    int nr,a,b;
    s=nr=0;

    //la inceput fiecare nod e intr-o multime diferita
    for(int i=1;i<=n;++i)
        M[i]=i;

    //ia fiecare muchie pe rand
    //pana cand avem n-1 muchii
    for(int i=1; i<=m && nr<n-1; ++i)
    {
        muchie x = mch[i];
        //daca nodurile se afla in multimi diferite
        //pune toate nodurile din multimea cu nr de ordine mai mare (b) in multimea cu nr de ordine mai mic (a)
        if(M[x.n1]!=M[x.n2])
        {
            if(M[x.n1]<M[x.n2])
                a=M[x.n1], b=M[x.n2];
            else
                a=M[x.n2], b=M[x.n1];
            for(int j=1;j<=n;++j)
                if(M[j]==b)
                    M[j]=a;
            ++nr;   //creste numarul de muchii
            s+=x.c; //adauga costul muchiei la suma
            mch[i].used=1;   //marcheaza muchia ca folosita
        }
    }
}

void afisare()
{
    out<<s<<""<<n-1<<"\n";
    for(int i=1;i<=n;++i)
        if(mch[i].used==1)
            out<<mch[i].n1<<" "<<mch[i].n2<<"\n";
}

int main()
{
    citire();
    quicksort(1,m); //sorteaza muchiile crescator in functie de cost
    kruskal();
    afisare();

    return 0;
}