#include<cstdio>
#include<algorithm>
#define maxN 200001
#define maxM 400001
using namespace std;
FILE* f=fopen("apm.in","r");
FILE* g=fopen("apm.out","w");
struct muchii{
    int x,y,c,luat;
};
muchii v[maxM];
int adanc[maxN],t[maxN],sol,radx,rady,n,m,nr;
bool cmp(muchii a,muchii b)
{
    return a.c<b.c;
}
void citire()
{
    int i;
    fscanf(f,"%d%d",&n,&m);
    for(i=1;i<=m;i++)
        {
            fscanf(f,"%d%d%d",&v[i].x,&v[i].y,&v[i].c);
        }
    sort(v+1,v+m+1,cmp);
}
int rad(int a)
{
    while(t[a])
        a=t[a];
    return a;
}
void uneste(int a,int b)
{
    if(adanc[a]==adanc[b])
    {
        t[a]=b;adanc[b]++;
    }
    else
        if(adanc[a]>adanc[b])
                t[b]=a;
            else t[a]=b;

}
void kruskal()
{
    int i;
    for(i=1;i<=m&&nr<n-1;i++)
    {
        radx=rad(v[i].x);
        rady=rad(v[i].y);
        if(radx!=rady)
        {
            uneste(radx,rady);
            sol+=v[i].c;
            v[i].luat=1;
            nr++;
        }
    }
}
void afisare()
{
    int i;
    fprintf(g,"%d \n%d\n",sol,n-1);
    for(i=1;i<=m;i++)
        if(v[i].luat)
            fprintf(g,"%d %d\n",v[i].x,v[i].y);
}
int main()
{
    citire();
    kruskal();
    afisare();
    return 0;
}