#include <algorithm>
using namespace std;
#define DMAX 200000
FILE*fin=fopen("apm.in","r");
FILE*fout=fopen("apm.out","w");
struct punct{
    int a;
    int b;
    int c;
};punct muchii[DMAX];
int n,m,h[DMAX],tata[DMAX],use[DMAX],cate;
void citire()
{
    fscanf(fin,"%d%d",&n,&m);
    for(int i=1;i<=m;i++)
        fscanf(fin,"%d%d%d",&muchii[i].a,&muchii[i].b,&muchii[i].c);
}
int cmp(const punct &a,const punct &b)
{
    return a.c<b.c;
}
void sortare()
{
    sort(muchii+1,muchii+m+1,cmp);
}
int cauta(int x)
{
    int r=x,aux;
    while(tata[r]!=0)
    {
        r=tata[r];
    }
    while(tata[x]!=0)
    {
        aux=tata[x];
        tata[x]=r;
        x=aux;
    }
    return r;
}
void unire(int a, int b)
{
    if(h[a]>h[b])
    {
        tata[b]=a;
    }
    else
        if(h[b]>h[a])
        {
            tata[a]=b;
        }
        else
        {
            tata[b]=a;
            h[a]++;
        }
}
int main()
{
    citire();
    sortare();
    for(int i=1;i<n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            int a=cauta(muchii[j].a);
            int b=cauta(muchii[j].b);
            if(a!=b&&use[j]==0)
            {
                use[j]=1;
                cate++;
                unire(a,b);
                break;
            }
        }
    }
    int s=0;
    for(int i=1;i<=m;i++)
        if(use[i]==1)
            s+=muchii[i].c;
    fprintf(fout,"%d\n%d\n",s,cate);
    for(int i=1;i<=m;i++)
        if(use[i]==1)
            fprintf(fout,"%d %d\n",muchii[i].a,muchii[i].b);
    return 0;
}