#include <cstdio>
#include <vector>
#include <algorithm>

using namespace std;

struct muchie{int c;int x;int y;}a[400001];
struct solutie{int x;int y;}sol[400001];
int n,m,minim,k;
int TT[400001],h[400001];
int interogate(int x)
{
    int i,aux;
    for(i=x;TT[i]!=i;i=TT[i]);
    while(TT[x]!=x)
    {
        aux=x;
        x=TT[x];
        TT[aux]=i;
    }
    return i;
}

void joint(int x,int y)
{
    if(h[x]>h[y]) TT[y]=x;
    else if(h[x]<h[y])TT[x]=y;
    else {TT[x]=y;h[y]++;}
}

int cmp(muchie a,muchie b)
{
    return a.c<b.c;
}

int main()
{
    int i;
    FILE *f=fopen("apm.in","r");
    FILE *g=fopen("apm.out","w");
    fscanf(f,"%d %d",&n,&m);
    for(i=1;i<=m;i++)
    {
        fscanf(f,"%d %d %d",&a[i].x,&a[i].y,&a[i].c);
    }
    for(i=1;i<=n;i++){TT[i]=i;h[i]=1;}
    sort(a+1,a+m+1,cmp);
    for(i=1;i<=m;i++)
    {
        if(interogate(a[i].x)!=interogate(a[i].y))
        {
            joint(interogate(a[i].x),interogate(a[i].y));
            minim+=a[i].c;
            sol[++k].x=a[i].x;
            sol[k].y=a[i].y;
        }
    }
    fprintf(g,"%d\n%d\n",minim,n-1);
    for(i=1;i<=k;i++)fprintf(g,"%d %d\n",sol[i].y,sol[i].x);
    fclose(f);
    fclose(g);
    return 0;
}