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

using namespace std;

struct MUCHIE{ int x,y,cost; } E[20];
int p[20],h[20],n,m;

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

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

void MakeSet(int i){

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

}
int FindSet(int i){

    if(p[i]==0)
        return i;
    else
        p[i]=FindSet(p[i]);
    return p[i];
    }
void Union(int i,int j){

    i=FindSet(i);
    j=FindSet(j);

    if(h[i]>h[j])
        p[j]=i;
    else
        {
            p[i]=j;
            if(h[i]==h[j])
                h[j]++;
        }
}
void citire(char* numeFisier){

    ifstream f(numeFisier);
    f>>n>>m;
    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();
    }


int main()
{
    ofstream f("apm.out");
    citire("apm.in");
    int s=0,k=0;
    for(int i=0;i<n;i++)
        MakeSet(i);
    for(int i=0;i<m;i++){
        if(FindSet(E[i].x)!=FindSet(E[i].y))
        {
            k++;
            s+=E[i].cost;
            f<<E[i].x<<" "<<E[i].y<<"\n";
            Union(E[i].x,E[i].y);
        }
        if(k==n-1)
            break;
    }
    f<<s<<" "<<k;
    f.close();
}