#include <stdio.h>
#include <algorithm>
using namespace std;
FILE *f,*g;

int n,m;
int tata[200002],rang[200002],sol[2][400002];

struct muchii
{
    int c,x,y;
}muchie[400002];

bool how(muchii &x, muchii &y)
{
        return x.c<y.c;
}

void read()
{
    fscanf(f,"%d %d",&n,&m);
    for(int i=1;i<=m;i++)
        fscanf(f,"%d %d %d",&muchie[i].x,&muchie[i].y,&muchie[i].c);
    for(int i=1;i<=n;i++)
        tata[i]=i,rang[i]=1;
    sort(muchie+1,muchie+m+1,how);
}

int Root(int x)
{
    while(x!=tata[x])
        x=tata[x];
    return x;
}

void unite(int x, int y)
{
    if(rang[x]>rang[y])
        tata[y]=x;
    else
        tata[x]=y;
    if(rang[y]==rang[x])
        rang[y]++;
}

int main()
{
    f=fopen("apm.in","r");
    g=fopen("apm.out","w");

    read();
    int rez=0,k=0;
    for(int i=1;i<=m;i++)
    {
        int xx=muchie[i].x;
        int yy=muchie[i].y;
        int cost=muchie[i].c;
        if(Root(xx)!=Root(yy))
        {
            unite(Root(xx),Root(yy));
            rez+=cost;
            sol[0][++k]=xx;
            sol[1][k]=yy;
        }
    }
    fprintf(g,"%d\n%d\n",rez,k);
    for(int i=1;i<=k;i++)
        fprintf(g,"%d %d\n",sol[1][i],sol[0][i]);
    return 0;
}