#include <cstdio>
#include <algorithm>

using namespace std;
FILE *f,*g;

int tata[200002],rang[200002];

struct bla
{
    int x,y,c;
}v[200002];
bool how(bla A, bla B)
{
    return (A.c<B.c);
}
struct
{
    int x,y;
}q[200002];

int root(int nod)
{
    while(nod!=tata[nod])
        nod=tata[nod];
    return nod;
}
void unite(int ra, int rb)
{
    if(rang[ra]<rang[rb])
        tata[ra]=rb;
    else
        tata[rb]=ra;
    if(rang[ra]==rang[rb])
        ++rang[ra];
}
int main()
{
    f=fopen("apm.in","r");
    g=fopen("apm.out","w");
    int n,m;
    fscanf(f,"%d %d",&n,&m);
    for(int 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,how);
    int a,b,ra,rb;
    for(int i=1;i<=n;++i)
        tata[i]=i;
    int nr=0,cost=0;

    for(int i=1;i<=m;++i)
    {
        a=v[i].x;
        b=v[i].y;
        ra=root(a);
        rb=root(b);
        if(ra!=rb)
        {
            cost+=v[i].c;
            unite(ra,rb);
            q[++nr]={a,b};
        }
    }
    fprintf(g,"%d\n%d\n",cost,nr);
    for(int i=1;i<=nr;++i)
    {
        fprintf(g,"%d %d\n",q[i].x,q[i].y);
    }
    return 0;
}