#include <iostream>
#include <fstream>
#include <stdlib.h>

using namespace std;

struct MUCHIE{ int x,y,cost; } ;

int comp(const void* a,const void* b){

    return ((MUCHIE*)a)->cost-((MUCHIE*)b)->cost;
    }

void MakeSet(int i,int *p,int* h){

    p[i]=0;
    h[i]=0;

}
int FindSet(int i,int *p,int n){
    if(i>=0&&i<n)
    {
        if(p[i]==0)
            return i;
        else
            p[i]=FindSet(p[i],p,n);
        return p[i];
    }
}
void Union(int i,int j,int *p,int *h,int n){

    i=FindSet(i,p,n);
    j=FindSet(j,p,n);

    if(h[i]>h[j])
        p[j]=i;
    else
        {
            p[i]=j;
            if(h[i]==h[j])
                h[j]++;
        }
}

int main(){

    int *p,*h,*r,n,m,s=0,k=0;
    MUCHIE *E;
    ifstream f("apm.in");

    f>>n>>m;
    p=new int[n];
    h=new int[n];
    r=new int[m];
    E=new MUCHIE[m];

    for(int i=0;i<m;i++)
        r[i]=0;

    for(int i=0;i<m;i++)
        f>>E[i].x>>E[i].y>>E[i].cost;

    qsort(E,m,sizeof(MUCHIE),comp);

    f.close();

    for(int i=0;i<n;i++)
        MakeSet(i,p,h);

    for(int i=0;i<m;i++){
        if(FindSet(E[i].x,p,n)!=FindSet(E[i].y,p,n))
        {
            k++;
            s+=E[i].cost;
            r[i]=1;
            Union(E[i].x,E[i].y,p,h,n);
        }
        if(k==n-1)
            break;
    }

    ofstream g("apm.out");

    g<<s<<" "<<k<<"\n";
    for(int i=0;i<m;i++)
        if(r[i])
            g<<E[i].x<<" "<<E[i].y<<"\n";
    g.close();
}