#include <cstdio>
#include <algorithm>

using namespace std;
FILE *f,*g;

struct bla
{
    int x,y,c;
}v[400002];
int rang[200002],tata[200002],ss,cost;
int m,n;
struct
{
    int x,y;
}sol[400002];

bool how(bla A, bla B)
{
    return (A.c<B.c);
}

int multime(int rad)
{
    while(rad!=tata[rad])
        rad=tata[rad];
    return rad;
}
void unite(int rada, int radb)
{
    if(rang[rada]<rang[radb])
        tata[rada]=radb;
    else
        tata[radb]=rada;
    if(rang[rada]==rang[radb])
        ++rang[rada];
}
int main()
{
    f=fopen("apm.in","r");
    g=fopen("apm.out","w");
    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);
    for(int i=1;i<=n;++i)
        tata[i]=i;
    int a,b,ma,mb;
    for(int i=1;i<=m;++i)
    {
        a=v[i].x;
        b=v[i].y;
        ma=multime(a);
        mb=multime(b);
        if(ma!=mb)
        {
            unite(ma,mb);
            cost+=v[i].c;
            ++ss;
            sol[ss].x=a;
            sol[ss].y=b;
        }
    }
    fprintf(g,"%d\n%d\n",cost,ss);
    for(int i=1;i<=ss;++i)
        fprintf(g,"%d %d\n",sol[i].x, sol[i].y);
    fclose(f);
    fclose(g);
    return 0;
}