#include <algorithm>
#include <cstring>
#include <fstream>
using namespace std;
#define DMAX 400005
FILE*fin=fopen("apm.in","r");
ofstream fout("apm.out");
struct punct{
    int a;
    int b;
    int c;
};punct muchii[DMAX];
int n,m,h[DMAX],tata[DMAX],use[DMAX],cate,sol[DMAX];
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();
    int ind=0;
    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;
                ind++;
                sol[ind]=j;
                cate++;
                unire(a,b);
                break;
            }
        }
    }
    int s=0;
    for(int i=1;i<=ind;i++)
            s+=muchii[sol[i]].c;
    fout<<s<<'\n'<<cate<<'\n';
    for(int i=1;i<=ind;i++)
            fout<<muchii[sol[i]].a<<' '<<muchii[sol[i]].b<<'\n';
    return 0;
}