#include <stdio.h>
#include <stdlib.h>
#include <ctype.h>
#include <algorithm>
using namespace std;
int n,m,i,x,y,l,c,j,cost,sol[400001],t[100001],nr,h[100001],a1,a2,*sx,*sy;
char *b;
struct muchie
{
    int x,y,c;
}M[400001];
bool sortare(muchie a,muchie b)
{
    return a.c<b.c;
}
int arb(int n)
{
    while (t[n]) n=t[n];
    return n;
}
void kruskal()
{
    int i,j=0;
    for (i=1;i<n;i++)
    {
        a1=a2;
        while (a1==a2)
        {
            a1=arb(M[++j].x);
            a2=arb(M[j].y);
        }
        cost+=M[j].c;
        sx[++nr]=M[j].x; sy[nr]=M[j].y;
        if (h[a1]>h[a2]) t[a2]=a1;
        else if (h[a1]<h[a2]) t[a1]=a2;
        else
        {
            t[a1]=a2;
            h[a2]++;
        }
    }
}
int main()
{
    freopen ("apm.in","r",stdin);
    freopen ("apm.out","w",stdout);
    scanf("%i%i",&n,&m);
    for (i=1;i<=m;i++)
        scanf("%i%i%i",&M[i].x,&M[i].y,&M[i].c);
    sx=(int*) malloc(n*sizeof(int));
    sy=(int*) malloc(n*sizeof(int));
    sort(M+1,M+m+1,sortare);
    kruskal();
    printf("%i\n%i\n",cost,nr);
    for (i=1;i<=nr;i++) printf("%i %i\n",sx[i],sy[i]);
    fclose(stdin);
    fclose(stdout);
    return 0;
}