#include <iostream>
#include<fstream>
#include<algorithm>
#define N 200000
#define inf 10000000
using namespace std;

ifstream fin("apm.in");
ofstream fout("apm.out");



int n,m;

struct muchie
{
    int x,y,cost;
    bool valid;//folosita sau nu

};

muchie a[400005];

void read()
{
    int i,j;
    fin>>n>>m;
    for(i=1;i<=m;++i)
        fin>>a[i].x>>a[i].y>>a[i].cost;

}

int pivotare(int s,int d)
{
    int pasi=0,pasj=1,i=s,j=d;
    int p=s+rand()%(d-s+1);
    muchie aux;
    aux=a[s];a[s]=a[p];a[p]=aux;

    while(i<j)
    {
        if(a[i].cost>a[j].cost)
        {
            swap(pasi,pasj);
            aux=a[i];a[i]=a[j];a[j]=aux;
        }
        i+=pasi;
        j-=pasj;
    }
    return i;

}

void qs(int s,int d)
{
    if(s<d)
    {
        int p=pivotare(s,d);
        qs(s,p-1);
        qs(p+1,d);

    }
}

void kruskal()
{
    qs(1,m);
    int i,cx,cy,j;
    /*for(i=1;i<=m;++i)
        cout<<a[i].x<<" "<<a[i].y<<" "<<a[i].cost<<"\n";*/
    int costarbore=0;
    int c[N];//din ce comp face parte fiecare nod
    int ct=0;//nr muchii selectate

    for(i=1;i<=n;++i)
        c[i]=i;
    for(i=1;i<=m&&ct<n-1;++i)//pt fiecare muchie
        if(c[a[i].x]!=c[a[i].y])//comp diferite
    {

        ct++;
        costarbore+=a[i].cost;
        a[i].valid=1;//fol muchie
        //unificam comp
        cx=c[a[i].x];cy=c[a[i].y];

        for(j=1;j<=n;++j)
            if(c[j]==cx)c[j]=cy;
    }

    fout<<costarbore<<"\n"<<n-1<<"\n";
}



void print()
{
   int i;
   for(i=1;i<=m;++i)
    if(a[i].valid)
        fout<<a[i].x<<" "<<a[i].y<<"\n";

}


int main()
{

    read();
    kruskal();
    print();



    return 0;
}